×

A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs. (English) Zbl 1339.05389

Summary: We prove new results for approximating the graphic TSP. Specifically, we provide a polynomial-time \(\frac{9}{7}\)-approximation algorithm for cubic bipartite graphs and a \((\frac{9}{7} + \frac{1}{21(k - 2)})\)-approximation algorithm for \(k\)-regular bipartite graphs, both of which are improved approximation factors compared to previous results. Our approach involves finding a cycle cover with relatively few cycles, which we are able to do by leveraging the fact that all cycles in bipartite graphs are of even length along with our knowledge of the structure of cubic graphs.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68W25 Approximation algorithms
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[2] Barnette, David W., Conjecture 5, Recent Prog. Combin., 343 (1969)
[3] Boyd, Sylvia; Sitters, René; van der Ster, Suzanne; Stougie, Leen, The traveling salesman problem on cubic and subcubic graphs, Math. Program., 144, 1-2, 227-245 (2014) · Zbl 1288.90136
[4] Christofides, Nicos, Worst-case Analysis of A New Heuristic for the Travelling Salesman Problem. Technical Report, GSIA (1976), Carnegie Mellon University
[5] Correa, José; Larré, Omar; Soto, José A., TSP tours in cubic graphs: beyond 4/3, SIAM J. Discrete Math., 29, 2, 915-939 (2015) · Zbl 1314.05199
[6] Dantzig, George; Fulkerson, Ray; Johnson, Selmer, Solution of a large-scale traveling-salesman problem, J. Oper. Res. Soc. Amer., 393-410 (1954) · Zbl 1414.90372
[7] Feige, Uri; Ravi, R.; Singh, Mohit, Short tours through large linear forests, (Integer Programming and Combinatoral Optimization (2014), Springer), 273-284 · Zbl 1418.90274
[8] Gamarnik, David; Lewenstein, Moshe; Sviridenko, Maxim, An improved upper bound for the TSP in cubic 3-edge-connected graphs, Oper. Res. Lett., 33, 5, 467-474 (2005) · Zbl 1195.90091
[9] Gharan, Shayan Oveis; Saberi, Amin; Singh, Mohit, A randomized rounding approach to the traveling salesman problem, (Foundations of Computer Science, FOCS, 2011 IEEE 52nd Annual Symposium on (2011), IEEE), 550-559 · Zbl 1292.68171
[10] Goemans, Michel X., Worst-case comparison of valid inequalities for the TSP, Math. Program., 69, 1-3, 335-349 (1995) · Zbl 0844.90101
[11] Hopcroft, John E.; Karp, Richard M., An nˆ5/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 4, 225-231 (1973) · Zbl 0266.05114
[12] Mömke, Tobias; Svensson, Ola, Approximating graphic TSP by matchings, (Foundations of Computer Science, FOCS, 2011 IEEE 52nd Annual Symposium on (2011), IEEE), 560-569 · Zbl 1292.68169
[14] Sebő, András; Vygen, Jens, Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs, Combinatorica (2014) · Zbl 1340.90201
[16] Vishnoi, Nisheeth K, A permanent approach to the traveling salesman problem, (Foundations of Computer Science, FOCS, 2012 IEEE 53rd Annual Symposium on (2012), IEEE), 76-80
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.