×

\(\frac{13}{9}\)-approximation for graphic TSP. (English) Zbl 1319.68255

Summary: The Travelling Salesman Problem is one of the fundamental and intensively studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides’s algorithm with an approximation factor of \(\frac{3}{2}\), even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only \(\frac{4}{3}\). Very recently, significant progress has been made for the important special case of graphic metrics, first by S. Oveis Gharan et al. [in: Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science, FOCS 2011. Los Alamitos, CA: IEEE Computer Society. 550–559 (2011; Zbl 1292.68171)], and then by T. Mömke and O. Svensson [ibid. 560–569 (2011; Zbl 1292.68169)]. In this paper, we provide an improved analysis of the approach presented by Mömke and Svensson [loc. cit.] yielding a bound of \(\frac{13}{9}\) on the approximation factor, as well as a bound of \(\frac{19}{12}+\varepsilon\) for any \(\varepsilon>0\) for a more general Travelling Salesman Path Problem in graphic metrics.

MSC:

68W25 Approximation algorithms
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks

References:

[1] An, H.-C.; Kleinberg, R.; Shmoys, D. B., Improving Christofides’ algorithm for the s-t path TSP, 875-886 (2012) · Zbl 1286.68173
[2] Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. Rep. 388, Graduate School of Industrial Administration, CMU (1976) · Zbl 1489.90150
[3] Cornuejols, G., Naddef, D., Fonlupt, J.: The traveling salesman problem on a graph and some related integer polyhedra. Math. Program. 33, 1-27 (1985) · Zbl 0562.90095 · doi:10.1007/BF01582008
[4] Goemans, M. X.; Bertsimas, D. J., On the parsimonious property of connectivity problems, 388-396 (1990) · Zbl 0800.68635
[5] Grigni, M.; Koutsoupias, E.; Papadimitriou, C. H., An approximation scheme for planar graph TSP, 640-645 (1995) · Zbl 0938.68748
[6] Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18(6), 1138-1162 (1970) · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[7] Hoogeveen, J.A.: Analysis of Christofides’ heuristic: some paths are more difficult than cycles. Oper. Res. Lett. 10(5), 291-295 (1991) · Zbl 0748.90071 · doi:10.1016/0167-6377(91)90016-I
[8] Mömke, T.; Svensson, O., Approximating graphic TSP by matchings, 560-569 (2011) · Zbl 1292.68169
[9] Sebő, A.: Eight fifth approximation for TSP paths (2012). arXiv:1209.3523 · Zbl 1336.90098
[10] Sebő, A., Vygen, J.: Shorter tours by nicer ears (2012). arXiv:1201.1870 · Zbl 1340.90201
[11] Mucha, M., 13/9-approximation for graphic TSP, 30-41 (2012) · Zbl 1245.68251
[12] Oveis Gharan, S.; Saberi, A.; Singh, M., A randomized rounding approach to the travelling salesman problem, 550-559 (2011) · Zbl 1292.68171
[13] Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1-12 (1993) · Zbl 0778.90057 · doi:10.1287/moor.18.1.1
[14] 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) · Zbl 0698.68050 · doi:10.1016/0020-0190(90)90028-V
[15] Wolsey, K.: Heuristic analysis, linear programming and branch and bound. Math. Program. Stud. 13, 121-134 (1980) · Zbl 0442.90061 · doi:10.1007/BFb0120913
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.