Top

Theory of Computing Systems

Published in:

04-11-2017

Maximum ATSP with Weights Zero and One via Half-Edges

Author: Katarzyna Paluch

Published in: Theory of Computing Systems | Issue 2/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Scheduling Parallel Jobs Online with Convex and Concave Parallelizability

next article Shortest Augmenting Paths for Online Matchings on Trees

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Bläser, M.: An 8/13-approximation algorithm for the asymmetric maximum TSP. J. Algorithms 50(1), 23–48 (2004)MathSciNetCrossRefMATH

Bläser, M.: A 3/4-approximation algorithm for maximum ATSP with weights zero and one. APPROX-RANDOM. In: Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 8th International Workshop on Randomization and Computation, vol. 3122 of Lecture Notes in Computer Science, pp. 61–71. Springer (2004)

Bläser, M., Siebert, B.: Computing cycle covers without short cycles. In: Proceedings of the 9th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computing Science, vol. 2161, pp 369–379, Springer (2001)

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’03MathSciNetCrossRefMATH

Karpinski, M., Schmied, R.: Improved inapproximability results for the shortest superstring and related problems. In: Proceedings of Nineteenth Computing: The Australasian Theory Symposium, CATS 2013, vol. 141 of CRPIT, pp. 27–36. Australian Computer Society (2013)

Kosaraju, S. R., Park, J. K., Stein, C.: Long tours and short superstrings. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp 166–177 (1994)

Lewenstein, M., Sviridenko, M.: A 5/8 approximation algorithm for the maximum asymmetric tsp. SIAM J. Discrete Math. 17(2), 237–248 (2003)MathSciNetCrossRefMATH

Micali, S., Vazirani, V. V.: An \(O(\sqrt {|V|} |E|)\) algorithm for finding maximum matching in general graphs. FOCS. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science, pp. 17–27. IEEE Computer Society (1980)

Paluch, K. E.: Maximum ATSP with weights zero and one via half-edges. In: Proceedings of the 13th International Workshop on Approximation and Online Algorithms (2015)

10.

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, vol. 14, pp 501–506 (2012)

11.

Paluch, K.: Better approximation algorithms for maximum asymmetric traveling salesman and shortest superstring. arXiv:1401.3670 (2014)

12.

Vishwanathan, S.: An approximation algorithm for the asymmetric travelling salesman problem with distances one and two. Inform. Proc. Lett. 44, 297–302 (1992)MathSciNetCrossRefMATH

Title: Maximum ATSP with Weights Zero and One via Half-Edges
Author: Katarzyna Paluch
Publication date: 04-11-2017
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 2/2018
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-017-9818-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2018

On the Smoothness of Paging Algorithms

Approximation Algorithms for Connected Graph Factors of Minimum Weight

Tight Bounds for Double Coverage Against Weak Adversaries

Constant-Time Local Computation Algorithms

WAOA 2015 Special Issue on TOCS

Efficient Vertex-Label Distance Oracles for Planar Graphs

Premium Partner