×
van Zuylen, Anke

Improved approximations for cubic bipartite and cubic TSP. (English) Zbl 1411.90303

Math. Program. 172, No. 1-2 (B), 399-413 (2018).
Summary: We show improved approximation guarantees for the traveling salesman problem on cubic bipartite graphs and cubic graphs. For connected cubic bipartite graphs with \(n\) nodes, we improve on recent results of Karp and Ravi by giving a “local improvement” algorithm that finds a tour of length at most \(5/4n-2\). For 2-connected cubic graphs, we show that the techniques of Mömke and Svensson can be combined with the techniques of Correa, Larré and Soto, to obtain a tour of length at most \((4/3-1/8754)n\).

MSC:

90C27 Combinatorial optimization
68W25 Approximation algorithms
68W40 Analysis of algorithms
05C85 Graph algorithms (graph-theoretic aspects)

Keywords:

traveling salesman problem; approximation algorithm; cubic bipartite graphs; cubic graphs; Barnette’s conjecture
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Aggarwal, N., Garg, N., Gupta, S.: A 4/3-approximation for TSP on cubic 3-edge-connected graphs. http://arxiv.org/abs/1101.5586 (2011)
[2] Barnette, D.: Conjecture 5. In: Tutte, W.T. (ed.) Recent progress in combinatorics: proceedings of the third waterloo conference on combinatorics, May 1968. Academic Press, New York (1969)
[3] Boyd, S.; Sitters, R.; Ster, S.; Stougie, L., The traveling salesman problem on cubic and subcubic graphs, Math. Program., 144, 227-245, (2014) · Zbl 1288.90136 · doi:10.1007/s10107-012-0620-1
[4] Candráková, B., Lukotka, R.: Cubic TSP—a 1.3-approximation. CoRR, abs/1506.06369 (2015)
[5] Christofides, N.: Worst Case Analysis of a New Heuristic for the Traveling Salesman Problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh (1976)
[6] Correa, José; Larré, Omar; Soto, José A., TSP Tours in Cubic Graphs: Beyond 4/3, SIAM Journal on Discrete Mathematics, 29, 915-939, (2015) · Zbl 1314.05199 · doi:10.1137/140972925
[7] Dantzig, GB; Fulkerson, DR; Johnson, SM, Solution of a large-scale traveling-salesman problem, Oper. Res., 2, 393-410, (1954) · Zbl 1414.90372
[8] Gamarnik, D.; Lewenstein, M.; Sviridenko, M., An improved upper bound for the TSP in cubic 3-edge-connected graphs, Oper. Res. Lett., 33, 467-474, (2005) · Zbl 1195.90091 · doi:10.1016/j.orl.2004.09.005
[9] Held, M.; Karp, RM, The traveling-salesman problem and minimum spanning trees, Oper. Res., 18, 1138-1162, (1970) · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[10] Karp, J., Ravi, R.: A 9/7-approximation algorithm for graphic TSP in cubic bipartite graphs. Discrete Appl. Math. 209, 164-216 (2016) (Preliminary version appeared in (APPROX-RANDOM 2014): pp. 284-296, 2014) · Zbl 1339.05389
[11] Mömke, T., Svensson, O.: Removing and adding edges for the traveling salesman problem. J. ACM 63(1), 2 (2016) (Preliminary version appeared in FOCS 2011: pp. 560-569, 2011) · Zbl 1426.90219
[12] Mucha, M.: 13/9 -approximation for graphic TSP. Theory Comput. Syst. 55(4), 640-657 (2014) (Preliminary version appeared in STACS 2012: 30-41, 2012) · Zbl 1319.68255
[13] Petersen, J., Die Theorie der regulären graphs, Acta Math., 15, 193-220, (1891) · JFM 23.0115.03 · doi:10.1007/BF02392606
[14] 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, 597-629, (2014) · Zbl 1340.90201 · doi:10.1007/s00493-014-2960-3
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.