科研之友
微信
新浪微博
Facebook
分享链接
摘要
We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph G that admits an orientation covering a nonnegative crossing G-supermodular demand function, as defined by Frank [J. Comb. Theory Ser. B, 28 (1980), pp. 251-261]. An important example is (k, t)-edge-connectivity, a common generalization of global and rooted edge-connectivity. Our algorithm is based on a nonstandard application of the iterative rounding method. We observe that the standard linear program with cut constraints is not amenable and use an alternative linear program with partition and copartition constraints instead. The proof requires a new type of uncrossing technique on partitions and copartitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. The problem becomes substantially more difficult already for the simpler requirement of k-edge-connectivity. Khanna, Naor, and Shepherd [SIAM J. Discrete Math., 19 (2005), pp. 245-257] showed that the integrality gap of the natural linear program is at most 4 when k = 1 and conjectured that it is constant for all fixed k. We disprove this conjecture by showing an Omega(vertical bar V vertical bar) integrality gap even when k = 2.
- 出版日期2018
