On the tree augmentation problem. (English) Zbl 1522.68417
Summary: In the Tree Augmentation problem we are given a tree \(T = (V, F)\) and a set \(E \subseteq V \times V\) of edges with positive integer costs \(\{c_e : e \in E\}\). The goal is to augment \(T\) by a minimum cost edge set \(J \subseteq E\) such that \(T \cup J\) is 2-edge-connected. We obtain the following results.
- –
- Recently, D. Adjiashvili [SODA 2017, 2384–2399 (2017; Zbl 1410.68268)] introduced a novel LP for the problem and used it to break the 2-approximation barrier for instances when the maximum cost \(M\) of an edge in \(E\) is bounded by a constant; his algorithm computes a \(1.96418 + \epsilon\) approximate solution in time \(n^{{(M/\epsilon^2)}^{O(1)}}\). Using a simpler LP, we achieve ratio \(\frac{12}{7} + \epsilon\) in time \(2^{O(M/\epsilon^2)} \operatorname{poly}(n)\). This gives ratio better than 2 for logarithmic costs, and not only for constant costs.
- –
- One of the oldest open questions for the problem is whether for unit costs (when \(M = 1)\) the standard LP-relaxation, so called Cut-LP, has integrality gap less than 2. We resolve this open question by proving that for unit costs the integrality gap of the Cut-LP is at most \(28/15 = 2 - 2/15\). In addition, we will prove that another natural LP-relaxation, that is much simpler than the ones in previous work, has integrality gap at most 7/4.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W25 | Approximation algorithms |
| 90C35 | Programming involving graphs or networks |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Citations:
Zbl 1410.68268References:
| [1] | Adjiashvili, D.: Beating approximation factor two for weighted tree augmentation with bounded costs. In: SODA, pp. 2384-2399 (2017) · Zbl 1410.68268 |
| [2] | Appa, G.; Kotnyek, B., Rational and integral \(k\)-regular matrices, Discrete Math., 275, 1-3, 1-15 (2004) · Zbl 1043.15011 · doi:10.1016/S0012-365X(03)00095-5 |
| [3] | Appa, G.; Kotnyek, B.; Papalamprou, K.; Pitsoulis, L., Optimization with binet matrices, Oper. Res. Lett., 35, 3, 345-352 (2007) · Zbl 1169.90407 · doi:10.1016/j.orl.2006.04.003 |
| [4] | Caprara, A.; Fischetti, M., \(\{0,1/2\}\)-Chvátal-Gomory cuts, Math. Programm., 74, 3, 221-235 (1996) · Zbl 0855.90088 · doi:10.1007/BF02592196 |
| [5] | Cheriyan, J., Gao, Z.: Approximating (unweighted) tree augmentation via lift-and-project, part II (2015). Manuscript · Zbl 1395.90233 |
| [6] | Cheriyan, J., Jordán, T., Ravi, R.: On 2-coverings and 2-packing of laminar families. In: ESA, pp. 510-520 (1999) · Zbl 0945.05014 |
| [7] | Cheriyan, J.; Karloff, H.; Khandekar, R.; Koenemann, J., On the integrality ratio for tree augmentation, Oper. Res. Lett., 36, 4, 399-401 (2008) · Zbl 1155.90466 · doi:10.1016/j.orl.2008.01.009 |
| [8] | Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 4, 305-337 (1973) · Zbl 0253.05131 · doi:10.1016/0012-365X(73)90167-2 |
| [9] | Cohen, N.; Nutov, Z., A \((1+\ln 2)\)-approximation algorithm for minimum-cost \(2\)-edge-connectivity augmentation of trees with constant radius, Theor. Comput. Sci., 489-490, 67-74 (2013) · Zbl 1294.05146 · doi:10.1016/j.tcs.2013.04.004 |
| [10] | Cygan, M.: Private communication (2016) |
| [11] | Cygan, M.; Fomin, F.; Kowalik, F.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2016), Berlin: Springer, Berlin · Zbl 1334.90001 |
| [12] | Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A 3/2-approximation for augmenting a connected graph into a two-connected graph. In: APPROX, pp. 90-101 (2001) · Zbl 1001.05113 |
| [13] | Even, G.; Feldman, J.; Kortsarz, G.; Nutov, Z., A 1.8-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2, ACM Trans. Algorithms, 5, 2, 1-17 (2009) · Zbl 1398.68670 · doi:10.1145/1497290.1497297 |
| [14] | Fiorini, S., Groß, M., J.Könemann, Sanitá, L.: A \(\frac{3}{2} \)-approximation algorithm for tree augmentation via chvátal-gomory cuts (2017). arXiv:1702.05567 · Zbl 1403.68347 |
| [15] | Frederickson, G.; Jájá, J., Approximation algorithms for several graph augmentation problems, SIAM J. Comput., 10, 270-283 (1981) · Zbl 0461.05040 · doi:10.1137/0210019 |
| [16] | Goemans, M., Goldberg, A., Plotkin, S., D. Shmoys, E.T., Williamson, D.: Improved approximation algorithms for network design problems. In: SODA, pp. 223-232 (1994) · Zbl 0873.68005 |
| [17] | Gomory, R., Outline of an algorithm for integer solutions to linear programs, Bull. Am. Math. Soc., 64, 5, 275-278 (1958) · Zbl 0085.35807 · doi:10.1090/S0002-9904-1958-10224-4 |
| [18] | Grandoni, F., Kalaitzis, C., Zenklusen, R.: Improved approximation for tree augmentation: saving by rewiring. In: STOC, pp. 632-645 (2018) · Zbl 1429.68190 |
| [19] | Hochbaum, D.; Megiddo, N.; Naor, J.; Tamir, A., Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, Math. Programm., 62, 69-83 (1993) · Zbl 0802.90080 · doi:10.1007/BF01585160 |
| [20] | Jain, K., A factor 2 approximation algorithm for the generalized steiner network problem, Combinatorica, 21, 1, 39-60 (2001) · Zbl 1107.68533 · doi:10.1007/s004930170004 |
| [21] | Khuller, S.; Thurimella, R., Approximation algorithms for graph augmentation, J. Algorithms, 14, 214-225 (1993) · Zbl 0764.68120 · doi:10.1006/jagm.1993.1010 |
| [22] | Kortsarz, G., Nutov, Z.: LP-relaxations for tree augmentation. In: APPROX-RANDOM, pp. 13:1-13:16 (2016) · Zbl 1398.90193 |
| [23] | Kortsarz, G.; Nutov, Z., A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2, ACM Trans. Algorithms, 12, 2, 23 (2016) · Zbl 1398.68679 · doi:10.1145/2786981 |
| [24] | Lau, LC; Ravi, R.; Singh, M., Iterative Methods in Combinatorial Optimization (2011), Cambridge: Cambridge University Press, Cambridge · Zbl 1247.90002 · doi:10.1017/CBO9780511977152 |
| [25] | Maduel, Y.; Nutov, Z., Covering a laminar family by leaf to leaf links, Discrete Appl. Math., 158, 13, 1424-1432 (2010) · Zbl 1209.05049 · doi:10.1016/j.dam.2010.04.002 |
| [26] | Marx, D.; Végh, L., Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation, ACM Trans. Algorithms, 11, 4, 27 (2015) · Zbl 1398.68255 · doi:10.1145/2700210 |
| [27] | Nagamochi, H., An approximation for finding a smallest \(2\)-edge connected subgraph containing a specified spanning tree, Discrete Appl. Math., 126, 83-113 (2003) · Zbl 1012.68226 · doi:10.1016/S0166-218X(02)00218-4 |
| [28] | Schrijver, A., Combinatorial Optimization. Polyhedra and Efficiency (2004), Berlin: Springer, Berlin · Zbl 1072.90030 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
