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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Automated Detection of Adverse Drug Reactions from Social Media Posts with Machine Learning Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Approximation Algorithms for the Maximum m-Peripatetic Salesman Problem

verfasst von : Edward Kh. Gimadi, Oxana Yu. Tsidulko

Erschienen in: Analysis of Images, Social Networks and Texts

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We consider the maximum m-Peripatetic Salesman Problem (MAX m-PSP), which is a natural generalization of the classic Traveling Salesman Problem. The problem is strongly NP-hard. In this paper we propose two polynomial approximation algorithms for the MAX m-PSP with different and identical weight functions, correspondingly. We prove that for random inputs uniformly distributed on the interval [a, b] these algorithms are asymptotically optimal for \(m=o(n)\). This means that with high probability their relative errors tend to zero as the number n of the vertices of the graph tends to infinity. The results remain true for the distributions of inputs that minorize the uniform distribution.

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 An Exact Polynomial Algorithm for the Outerplanar Facility Location Problem with Improved Time Complexity
Nächstes Kapitel A Randomized Algorithm for 2-Partition of a Sequence
Literatur
1.
Ageev, A.A., Baburin, A.E., Gimadi, E.K.: A 3/4 approximation algorithms for finding two disjoint Hamiltonian cycles of maximum weight. J. Appl. Indust. Math. 1(2), 142–147 (2007)CrossRef
2.
Angluin, D., Valiant, L.G.: Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comp. Syst. Sci. 18(2), 155–193 (1979)MathSciNetCrossRefMATH
3.
Baburin, A.E., Gimadi, E.K.: On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional euclidean space. Proc. Steklov Inst. Math. 272(1), 1–13 (2011)MathSciNetCrossRefMATH
4.
Bollobás, B., Fenner, T.I., Frieze, A.M.: An algorithm for finding Hamilton paths and cycles in random graphs. Combinatorica 7, 327–341 (1987)MathSciNetCrossRefMATH
5.
Climer, S., Zhang, W.: Rearrangement clustering: pitfalls, remedies, and applications. JMLR 7, 919–943 (2006)MathSciNetMATH
6.
De Kort, J.B.J.M.: Upper bounds and lower bounds for the symmetric K-Peripatetic Salesman Problem. Optimization 23(4), 357–367 (1992)MathSciNetCrossRefMATH
7.
De Kort, J.B.J.M.: A branch and bound algorithm for symmetric 2-Peripatetic Salesman Problems. Eur. J. Oper. Res. 70, 229–243 (1993)CrossRefMATH
8.
Duchenne, E., Laporte, G., Semet, F.: The undirected m-Peripatetic Salesman Problem: polyhedral results and new algorithms. J. Oper. Res. 55(5), 949–965 (2007)MathSciNetCrossRefMATH
9.
10.
Gimadi, E.K., Glazkov, Y.V., Tsidulko, O.Y.: The probabilistic analysis of an algorithm for solving the m-planar 3-dimensional assignment problem on one-cycle permutations. J. Appl. Ind. Math. 8(2), 208–217 (2014)MathSciNetCrossRefMATH
11.
Gimadi, E.K., Istomin, A.M., Tsidulko, O.Y.: On asymptotically optimal approach to the m-Peripatetic Salesman Problem on random inputs. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 136–147. Springer, Cham (2016). https://​doi.​org/​10.​1007/​978-3-319-44914-2_​11 CrossRef
12.
Gimadi, E.K., Ivonina, E.V.: Approximation algorithms for the maximum 2-Peripatetic Salesman Problem. J. Appl. Ind. Math. 6(3), 295–305 (2012)MathSciNetCrossRefMATH
13.
14.
Glebov, A.N., Zambalaeva, D.Z.: A polynomial algorithm with approximation ratio 7/9 for the maximum two Peripatetic Salesmen Problem. J. Appl. Ind. Math. 6(1), 69–89 (2012)MathSciNetCrossRef
15.
Johnson, D.S., Krishnan, S., Chhugani, J., Kumar, S., Venkatasubramanian, S.: Compressing large boolean matrices using reordering techniques. In: 30th International Conference on Very Large Databases (VLDB), pp. 13–23 (2004)
16.
Johnson, O., Liu, J.: A traveling salesman approach for predicting protein functions. Source Code Biol. Med. 1(3), 9–16 (2006)
17.
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)MathSciNetCrossRefMATH
18.
Komlos, J., Szemeredi, E.: Limit distributions for the existence of Hamilton circuits in a random graph. Discrete Math. 43, 55–63 (1983)MathSciNetCrossRefMATH
19.
Krarup, J.: The Peripatetic Salesman and some related unsolved problems. In: Combinatorial Programming, Methods and Applications, pp. 173–178. Reidel, Dordrecht (1975)
20.
Petrov, V.V.: Limit Theorems of Probability Theory. Sequences of Independent Random Variables. Clarendon Press, Oxford (1995)MATH
21.
Ray, S.S., Bandyopadhyay, S., Pal, S.K.: Gene ordering in partitive clustering using microarray expressions. J. Biosci. 32(5), 1019–1025 (2007)CrossRef
22.
Song, L., Zhang, Yu., Peng, X., Wang, Z., Gildea, D.: AMR-to-text generation as a Traveling Salesman Problem. In: Proceedings of 2016 Conference on Empirical Methods in Natural Language Processing (2016)
Metadaten
Titel
Approximation Algorithms for the Maximum m-Peripatetic Salesman Problem
verfasst von
Edward Kh. Gimadi
Oxana Yu. Tsidulko
Copyright-Jahr
2018
Buch
Analysis of Images, Social Networks and Texts

Print ISBN: 978-3-319-73012-7

Electronic ISBN: 978-3-319-73013-4

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-73013-4_28

Premium Partner

    Bildnachweise