Abstract
We consider an APX-hard variant (Δ-Max-ATSP) and an APX-hard relaxation (Max-3-DCC) of the classical traveling salesman problem. Δ-Max-ATSP is the following problem: Given an edge-weighted complete loopless directed graph G such that the edge weights fulfill the triangle inequality, find a maximum weight Hamiltonian tour of G. We present a \(\frac{31}{40}\)-approximation algorithm for Δ-Max-ATSP with polynomial running time. Max-3-DCC is the following problem: Given an edge-weighted complete loopless directed graph, compute a spanning collection of node-disjoint cycles, each of length at least three, whose weight is maximum among all such collections. We present a \(\frac{3}{4}\)-approximation algorithm for this problem with polynomial running time. In both cases, we improve on the previous best approximation performances. The results are obtained via a new decomposition technique for the fractional solution of an LP formulation of Max-3-DCC.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bläser, M.: An \(\frac 8{13}\)-approximation algorithm for the asymmetric maximum tsp. J. Algorithms 50(1), 23–48 (2004)
Bläser, M., Manthey, B.: Two approximation algorithms for 3-cycle covers. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 40–50. Springer, Heidelberg (2002)
Bläser, M., Manthey, B.: Approximating maximum weight cycle covers in directed graphs with edge weights zero and one. Algorithmica (2005)
Breslauer, D., Jiang, T., Jiang, Z.: Rotations of periodic strings and short superstrings. J. Algorithms 24, 340–353 (1997)
Chalasani, P., Motwani, R.: Approximating capacitated routing and delivery problems. SIAM J. Comput. 28, 2133–2149 (1999)
Fisher, M.L., Nemhauser, L., Wolsey, L.A.: An analysis of approximations for finding a maximum weight Hamiltonian circuit. Networks 12(1), 799–809 (1979)
Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs. In: Proc. 44th Ann. IEEE Symp. on Foundations of Comput. Sci. (FOCS), pp. 56–65 (2003)
Kosaraju, S.R., Park, J.K., Stein, C.: Long tours and short superstrings. In: Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci, FOCS (1994)
Kostochka, A.V., Serdyukov, A.I.: Polynomial algorithms with the estimates \(\frac{3}{4}\) and \(\frac {5}{6}\) for the traveling salesman problem of the maximum. Upravlyaemye Sistemy 26, 55–59 (1985) (in Russian)
Lewenstein, M., Sviridenko, M.: A 5/8 approximation algorithm for the maximum asymmetric TSP. SIAM J. Disc. Math. 17(2), 237–248 (2003)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs (1982)
Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Operations Research 18, 1–11 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bläser, M., Ram, L.S., Sviridenko, M. (2005). Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems. In: Dehne, F., López-Ortiz, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2005. Lecture Notes in Computer Science, vol 3608. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11534273_31
Download citation
DOI: https://doi.org/10.1007/11534273_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28101-6
Online ISBN: 978-3-540-31711-1
eBook Packages: Computer ScienceComputer Science (R0)