Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Approximation Algorithms for k-Connected Graph Factors Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Maximum ATSP with Weights Zero and One via Half-Edges

verfasst von : Katarzyna Paluch

Erschienen in: Approximation and Online Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows
Nächstes Kapitel An FPT 2-Approximation for Tree-cut Decomposition
Literatur
1.
2.
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) CrossRef
3.
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) CrossRef
4.
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)
5.
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)MATHMathSciNetCrossRef
6.
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’03MathSciNetCrossRef
7.
Karpinski, M., Schmied, R.: Improved Inapproximability results for the shortest superstring and related problems. In: CATS, pp. 27–36 (2013)
8.
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)
9.
Kowalik, L., Mucha, M.: Deterministic 7/8-approximation for the metric maximum tsp. Theor. Comput. Sci. 410(47–49), 5000–5009 (2009)MATHMathSciNetCrossRef
10.
Kowalik, L., Mucha, M.: 35/44-approximation for asymmetric maximum tsp with triangle inequality. Algorithmica 59(2), 240–255 (2011)MATHMathSciNetCrossRef
11.
Lewenstein, M., Sviridenko, M.: A 5/8 approximation algorithm for the maximum asymmetric tsp. SIAM J. Discrete Math. 17(2), 237–248 (2003)MATHMathSciNetCrossRef
12.
Lovasz, L., Plummer, M.D.: Matching Theory (1986)
13.
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) CrossRef
14.
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)
15.
Paluch, K.: Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring. CoRR abs/1401.3670 (2014)
16.
Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1–11 (1993)MATHMathSciNetCrossRef
17.
Vishwanathan, S.: An approximation algorithm for the asymmetric travelling salesman problem with distances one and two. Inform. Proc. Lett. 44, 297–302 (1992)MATHMathSciNetCrossRef
Metadaten
Titel
Maximum ATSP with Weights Zero and One via Half-Edges
verfasst von
Katarzyna Paluch
Copyright-Jahr
2015
Buch
Approximation and Online Algorithms

Print ISBN: 978-3-319-28683-9

Electronic ISBN: 978-3-319-28684-6

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-28684-6_3