Abstract
Motivated by the well known “four-thirds conjecture” for the traveling salesman problem (TSP), we study the problem of uniform covers. A graph \(G=(V,E)\) has an \(\alpha \)-uniform cover for TSP (2EC, respectively) if the everywhere \(\alpha \) vector (i.e., \(\{\alpha \}^{E}\)) dominates a convex combination of incidence vectors of tours (2-edge-connected spanning multigraphs, respectively). The polyhedral analysis of Christofides’ algorithm directly implies that a 3-edge-connected, cubic graph has a 1-uniform cover for TSP. Sebő asked if such graphs have \((1-\epsilon )\)-uniform covers for TSP for some \(\epsilon > 0\). Indeed, the four-thirds conjecture implies that such graphs have \(\frac{8}{9}\)-uniform covers. We show that these graphs have \(\frac{18}{19}\)-uniform covers for TSP. We also study uniform covers for 2EC and show that the everywhere \(\frac{15}{17}\) vector can be efficiently written as a convex combination of 2-edge-connected spanning multigraphs. For a weighted, 3-edge-connected, cubic graph, our results show that if the everywhere \(\frac{2}{3}\) vector is an optimal solution for the subtour elimination linear programming relaxation for TSP, then a tour with weight at most \(\frac{27}{19}\) times that of an optimal tour can be found efficiently. Node-weighted, 3-edge-connected, cubic graphs fall into this category. In this special case, we can apply our tools to obtain an even better approximation guarantee. An essential ingredient in our proofs is decompositions of graphs (e.g., cycle covers) that cover small-cardinality cuts an even (nonzero) number of times. Another essential tool we use is half-integral tree augmentation, which is known to have a small integrality gap. To extend our approach to input graphs that are 2-edge-connected, we present a procedure to decompose a point in the subtour elimination polytope into spanning, connected subgraphs that cover each 2-edge cut an even number of times. Using this decomposition, we obtain a \(\frac{17}{12}\)-approximation algorithm for minimum weight 2-edge-connected spanning subgraphs on subcubic, node-weighted graphs.
Similar content being viewed by others
Notes
References
Boyd, S., Carr, R.: Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optim. 8(4), 525–539 (2011)
Boyd, S., Yao, F., Sun, Y.: A 5/4-approximation for subcubic 2EC using circulations and obliged edges. Discrete Appl. Math. 209, 48–58 (2016)
Boyd, S., Iwata, S., Takazawa, K.: Finding 2-factors closer to TSP tours in cubic graphs. SIAM J. Discrete Math. 27(2), 918–939 (2013)
Boyd, S., Legault, P.: Toward a 6/5 bound for the minimum cost 2-edge connected spanning subgraph. SIAM J. Discrete Math. 31(1), 632–644 (2017)
Boyd, S., Sebő, A.: The salesman’s improved tours for fundamental classes. In: Proceedings of 19th International Conference on Integer Programming and Combinatorial Optimization, pp. 111–122 (2017)
Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: The traveling salesman problem on cubic and subcubic graphs. Math. Program. 144(1–2), 227–245 (2014)
Christofides, N.: Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Technical report, Graduate School of Industrial Administration, Carnegie Mellon University (1976)
Cheriyan, J., Jordán, T., Ravi, R.: On 2-coverings and 2-packings of laminar families. In: European Symposium on Algorithms, pp. 510–520. Springer, Berlin (1999)
Cheriyan, J., Karloff, H., Khandekar, R., Könemann, J.: On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4), 399–401 (2008)
Carr, R., Ravi, R.: A new bound for the 2-edge connected subgraph problem. In: Proceedings of 6th International Conference on Integer Programming and Combinatorial Optimization, pp. 112–125. Springer, Berlin (1998)
Carr, R., Vempala, S.: On the Held–Karp relaxation for the asymmetric and symmetric traveling salesman problems. Math. Program. 100(3), 569–587 (2004)
Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5(1), 88–124 (1973)
Frederickson, G.N., Ja’Ja’, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10(2), 270–283 (1981)
Frederickson, G.N., Ja’Ja’, J.: On the relationship between the biconnectivity augmentation and traveling salesman problems. Theor. Comput. Sci. 19(2), 189–201 (1982)
Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5(1), 25–53 (1992)
Goemans, M.X., Bertsimas, D.J.: Survivable networks, linear programming relaxations and the parsimonious property. Math. Program. 60(1), 145–166 (1993)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)
Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69(1), 335–349 (1995)
Iglesias, J., Ravi, R.: Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem. ar**v:1707.05240 (2017)
Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39–60 (2001)
Kaiser, T., Škrekovski, R.: Cycles intersecting edge-cuts of prescribed sizes. SIAM J. Discrete Math. 22(3), 861–874 (2008)
Legault, P.: Towards New Bounds for the 2-Edge Connected Spanning Subgraph Problem. Master’s thesis, University of Ottawa (2017)
Monma, C.L., Munson, B.S., Pulleyblank, W.R.: Minimum-weight two-connected spanning networks. Math. Program. 46(1), 153–171 (1990)
Mömke, T., Svensson, O.: Removing and adding edges for the traveling salesman problem. J. ACM 63(1), 2 (2016)
Mucha, M.: 13/9-approximation for graphic TSP. Theory Comput. Syst. 55(4), 640–657 (2014)
Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pp. 550–559. IEEE (2011)
Sebő, A., Benchetrit, Y., Stehlik, M.: Problems about uniform covers, with tours and detours. Mathematisches Forschungsinstitut Oberwolfach Report 51, 2912–2915 (2014)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)
Sebő, A., Vygen, J.: Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica 34(5), 597–629 (2014)
Shmoys, D.B., Williamson, D.P.: Analyzing the Held–Karp TSP bound: a monotonicity property with application. Inf. Process. Lett. 35(6), 281–285 (1990)
Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. In: Rayward-Smith, V.J. (ed.) Combinatorial Optimization II, pp. 121–134. Springer, Berlin (1980)
Acknowledgements
We would like to thank Jennifer Iglesias for discussions on the tree augmentation problem, Gérard Cornuéjols for his comments on a preliminary draft of this paper, and Sylvia Boyd for clarifications regarding recent work on the 2EC problem. We thank an anonymous referee for pointing out an error in a previous version: we had claimed a smaller approximation ratio in the statement of Theorem 4. The work of A. Haddadan and R. Ravi is supported in part by the U. S. Office of Naval Research under Award Numbers N00014-12-1-1001 and N00014-18-1-2099, and the U. S. National Science Foundation under Award Number CCF-1527032. The work of A. Newman is supported in part by LabEx PERSYVAL-Lab (ANR 11-LABX-0025) and IDEX-IRS SACRE. Our joint work was also supported by a research grant from the Carnegie Bosch Institute.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Haddadan, A., Newman, A. & Ravi, R. Shorter tours and longer detours: uniform covers and a bit beyond. Math. Program. 185, 245–273 (2021). https://doi.org/10.1007/s10107-019-01426-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-019-01426-8