Abstract
In the maximum traveling salesman problem (Max TSP) we are given a complete undirected graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight. We present a fast combinatorial \(\frac{4}{5}\) – approximation algorithm for Max TSP. The previous best approximation for this problem was \(\frac{7}{9}\). The new algorithm is based on a technique of eliminating difficult subgraphs via gadgets with half-edges, a new method of edge coloring and a technique of exchanging edges.
Partly supported by Polish National Science Center grant UMO-2013/11/B/ST6/01748.
J. Marcinkowski—Partially supported by Polish NSC grant 2015/18/E/ST6/00456.
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
Arkin, E.M., Chiang, Y., Mitchell, J.S.B., Skiena, S., Yang, T.: On the maximum scatter TSP (extended abstract). In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 211–220 (1997)
Barvinok, A.I., Fekete, S.P., Johnson, D.S., Tamir, A., Woeginger, G.J., Woodroofe, R.: The geometric maximum traveling salesman problem. J. ACM 50(5), 641–664 (2003)
Barvinok, A., Johnson, D.S., Woeginger, G.J., Woodroofe, R.: The maximum traveling salesman problem under polyhedral norms. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 195–201. Springer, Heidelberg (1998). doi:10.1007/3-540-69346-7_15
Bhatia, R.: Private communication
Chalasani, P., Motwani, R.: Approximating capacitated routing and delivery problems. SIAM J. Comput. 28(6), 2133–2149 (1999)
Chen, Z.Z., Okamoto, Y., Wang, L.: Improved deterministic approximation algorithms for max TSP. Inf. Process. Lett. 95(2), 333–342 (2005)
Chen, Z.-Z., Wang, L.: An improved approximation algorithm for the bandpass-2 problem. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 188–199. Springer, Heidelberg (2012). doi:10.1007/978-3-642-31770-5_17
Chiang, Y.J.: New approximation results for the maximum scatter tsp. Algorithmica 41(4), 309–341 (2005)
Dudycz, S., Marcinkowski, J., Paluch, K.E., Rybicki, B.: A 4/5 - approximation algorithm for the maximum traveling salesman problem. CoRR abs/1512.09236 (2015). http://arxiv.org/abs/1512.09236
Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for finding a maximum weight hamiltonian circuit. Oper. Res. 27(4), 799–809 (1979)
Hassin, R., Levin, A., Rubinstein, S.: Approximation algorithms for maximum latency and partial cycle cover. Discrete Optim. 6(2), 197–205 (2009)
Hassin, R., Rubinstein, S.: An approximation algorithm for the maximum traveling salesman problem. Inf. Process. Lett. 67(3), 125–130 (1998)
Hassin, R., Rubinstein, S.: Better approximations for max TSP. Inf. Process. Lett. 75(4), 181–186 (2000)
Hassin, R., Rubinstein, S.: An approximation algorithm for maximum triangle packing. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 403–413. Springer, Heidelberg (2004). doi:10.1007/978-3-540-30140-0_37
Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs. In: 44th Symposium on Foundations of Computer Science (FOCS 2003) (2003)
Kosaraju, S.R., Park, J.K., Stein, C.: Long tours and short superstrings. In: 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1994)
Kowalik, Ł., Mucha, M.: 35/44-approximation for asymmetric maximum TSP with triangle inequality. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 589–600. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73951-7_51
Kowalik, Ł., Mucha, M.: Deterministic 7/8-approximation for the metric maximum TSP. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX/RANDOM -2008. LNCS, vol. 5171, pp. 132–145. Springer, Heidelberg (2008). doi:10.1007/978-3-540-85363-3_11
Monnot, J.: Approximation algorithms for the maximum hamiltonian path problem with specified endpoint(s). Eur. J. Oper. Res. 161(3), 721–735 (2005)
Paluch, K.E.: Better approximation algorithms for maximum asymmetric traveling salesman and shortest superstring. CoRR (2014)
Paluch, K.E., Elbassioni, K.M., van Zuylen, A.: Simpler approximation of the maximum asymmetric traveling salesman problem. In: 29th International Symposium on Theoretical Aspects of Computer Science, STACS (2012)
Paluch, K., Mucha, M., Ma̧dry, A.: A 7/9 - approximation algorithm for the maximum traveling salesman problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX/RANDOM -2009. LNCS, vol. 5687, pp. 298–311. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03685-9_23
Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1–11 (1993)
Schrijver, A.: Nonbipartite matching and covering. In: Combinatorial Optimization, vol. A, pp. 520–561. Springer (2003)
Serdyukov, A.I.: An algorithm with an estimate for the traveling salesman problem of maximum. Upravlyaemye Sistemy 25, 80–86 (1984) (in Russian)
Sichen, Z., Zhao, L., Liang, Y., Zamani, M., Patro, R., Chowdhury, R., Arkin, E.M., Mitchell, J.S.B., Skiena, S.: Optimizing read reversals for sequence compression. In: Pop, M., Touzet, H. (eds.) WABI 2015. LNCS, vol. 9289, pp. 189–202. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48221-6_14
Tong, W., Goebel, R., Liu, T., Lin, G.: Approximation algorithms for the maximum multiple RNA interaction problem. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 49–59. Springer, Cham (2013). doi:10.1007/978-3-319-03780-6_5
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Dudycz, S., Marcinkowski, J., Paluch, K., Rybicki, B. (2017). A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem. In: Eisenbrand, F., Koenemann, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2017. Lecture Notes in Computer Science(), vol 10328. Springer, Cham. https://doi.org/10.1007/978-3-319-59250-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-59250-3_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59249-7
Online ISBN: 978-3-319-59250-3
eBook Packages: Computer ScienceComputer Science (R0)