Abstract
We present a fast combinatorial 3 / 4-approximation algorithm for the maximum asymmetric TSP with weights zero and one. The approximation factor of this algorithm matches the currently best one given by Bläser in 2004 and based on linear programming. Our algorithm first computes a maximum size matching and a maximum weight cycle cover without certain cycles of length two but possibly with half-edges - a half-edge of a given edge e is informally speaking a half of e that contains one of the endpoints of e. Then from the computed matching and cycle cover it extracts a set of paths, whose weight is large enough to be able to construct a traveling salesman tour with the claimed guarantee.
Partly supported by Polish National Science Center grant UMO-2013/11/B/ST6/01748.
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
Bläser, M.: An 8/13-approximation algorithm for the asymmetric maximum TSP. J. Algorithms 50(1), 23–48 (2004)
Bläser, M.: A 3/4-approximation algorithm for maximum ATSP with weights zero and one. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol. 3122, pp. 61–71. Springer, Heidelberg (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, p. 40. Springer, Heidelberg (2002)
Bläser, M., Siebert, B.: Computing cycle covers without short cycles. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 369–379. Springer, Heidelberg (2001)
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)
Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs. J. ACM 52(4), 602–626 (2005). Preliminary version appeared in FOCS’03
Karpinski, M., Schmied, R.: Improved Inapproximability results for the shortest superstring and related problems. In: CATS, pp. 27–36 (2013)
Kosaraju, S.R., Park, J.K., Stein, C.: Long tours and short superstrings (preliminary version). In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 166–177 (1994)
Kowalik, L., Mucha, M.: Deterministic 7/8-approximation for the metric maximum tsp. Theor. Comput. Sci. 410(47–49), 5000–5009 (2009)
Kowalik, L., Mucha, M.: 35/44-approximation for asymmetric maximum tsp with triangle inequality. Algorithmica 59(2), 240–255 (2011)
Lewenstein, M., Sviridenko, M.: A 5/8 approximation algorithm for the maximum asymmetric tsp. SIAM J. Discrete Math. 17(2), 237–248 (2003)
Lovasz, L., Plummer, M.D.: Matching Theory (1986)
Paluch, K., Mucha, M., Madry, A.: A 7/9 - approximation algorithm for the maximum traveling salesman problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. LNCS, vol. 5687, pp. 298–311. Springer, Heidelberg (2009)
Paluch, K.E., Elbassioni, K.M., van Zuylen, A.: Simpler approximation of the maximum asymmetric traveling salesman problem. In: Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science, STACS 2012, Leibniz International Proceedings of Informatics 14, pp. 501–506 (2012)
Paluch, K.: Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring. CoRR abs/1401.3670 (2014)
Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1–11 (1993)
Vishwanathan, S.: An approximation algorithm for the asymmetric travelling salesman problem with distances one and two. Inform. Proc. Lett. 44, 297–302 (1992)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Paluch, K. (2015). Maximum ATSP with Weights Zero and One via Half-Edges. In: Sanità, L., Skutella, M. (eds) Approximation and Online Algorithms. WAOA 2015. Lecture Notes in Computer Science(), vol 9499. Springer, Cham. https://doi.org/10.1007/978-3-319-28684-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-28684-6_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-28683-9
Online ISBN: 978-3-319-28684-6
eBook Packages: Computer ScienceComputer Science (R0)