Abstract
Hamiltonian path problem is one of the fundamental problems in graph theory, the aim is to find a path in the graph that visits each vertex exactly once. In this paper, we consider a generalizedized problem: given a complete weighted undirected graph \(G=(V,E,c)\), two specified vertices s and t, let \(V^{\prime }\) and \(E^{\prime }\) be subsets of V and E, respectively. We aim to find an s-t path which visits each vertex of \(V^{\prime }\) and each edge of \(E^{\prime }\) exactly once with minimum cost. Based on LP rounding technique, we propose a \(\frac{9-\sqrt{33}}{2}\)-approximation algorithm.
X. Zhang–This research is supported or partially supported by the National Natural Science Foundation of China (Grant Nos. 11871280 and 11871081) and Qinglan Project.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
An, H.-C., Kleinberg, R., Shmoys, D.-B.: Improving Christofides’ algorithm for the \(s\)-\(t\) path TSP. J. ACM 62(5), 34 (2015)
Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Carnegie-Mellon University of Pittsburgh Pa Management Sciences Research Group (1976)
Cunningham, W.-H.: Testing membership in matroid polyhedra. J. Comb. Theory Ser. B 36(2), 161–188 (1984)
Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. 2(4), 393–410 (1954)
Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1(1), 127–136 (1971)
Edmonds, J., Johnson, E.-L.: Matching, Euler tours and the Chinese postman. Math. Program. 5(1), 88–124 (1973)
Frederickson, G.-N.: Approximation algorithms for some postman problems. J. ACM 26, 538–554 (1979)
Fumei, L., Alantha, N.: Traveling salesman path problems. Math. Progrom. 13, 39–59 (2008)
Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197 (1981)
Gutin, G., Punnen, A.: The Traveling Salesman Problem and its Variations. Kluwer, Dordrecht (2002)
Guttmann-Beck, N., Hassin, R., Khuller, S., Raghavachari, B.: Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28, 422–437 (2000)
Hoogeveen, J.-A.: Analysis of Christofides’ heuristic: some paths are more difficult than cycles. Oper. Res. Lett. 10, 291–295 (1991)
Karlin, A.-R., Klein, N., Gharan, S.-O.: A (slightly) improved approximation algorithm for metric TSP. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 32–45 (2021)
Karp, R.-M.: Reducibility among combinatorial problems. Complex. Comput. Comput. 2, 85–103 (1972)
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, 640–657 (2014)
Gharan, S.-O., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem (2011)
Sahni, S., Gonzales, T.: \(P\)-complete approximation problems. J. ACM 23(3), 555–565 (1976)
Sebő, A.: Eight-Fifth approximation for the path TSP. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 362–374. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36694-9_31
Sebö, A., Van Zuylen, A.: The salesman’s improved paths through forests. J. ACM 66(4), 28 (2019)
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). https://doi.org/10.1007/s00493-014-2960-3
Traub, V., Vygen, J.: Approaching \(\frac{3}{2}\) for the \(s\)-\(t\) path TSP. J. ACM 66(2), 14 (2019)
Zenklusen, R.-A.: \(1.5\)-Approximation for path TSP. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1539–1549 (2019)
Zhang, X., Du, D., Gutin, G., Ming, Q., Sun, J.: Approximation algorithms for general cluster routing problem. In: Kim, D., Uma, R.N., Cai, Z., Lee, D.H. (eds.) COCOON 2020. LNCS, vol. 12273, pp. 472–483. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-58150-3_38
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Sun, J., Gutin, G., Zhang, X. (2021). A LP-based Approximation Algorithm for generalized Traveling Salesperson Path Problem. In: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Combinatorial Optimization and Applications. COCOA 2021. Lecture Notes in Computer Science(), vol 13135. Springer, Cham. https://doi.org/10.1007/978-3-030-92681-6_50
Download citation
DOI: https://doi.org/10.1007/978-3-030-92681-6_50
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92680-9
Online ISBN: 978-3-030-92681-6
eBook Packages: Computer ScienceComputer Science (R0)