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:
On the Effect of Scalarising Norm Choice in a ParEGO implementation Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

The Multiobjective Shortest Path Problem Is NP-Hard, or Is It?

verfasst von : Fritz Bökler

Erschienen in: Evolutionary Multi-Criterion Optimization

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

To show that multiobjective optimization problems like the multiobjective shortest path or assignment problems are hard, we often use the theory of \(\mathbf {NP} \)-hardness. In this paper we rigorously investigate the complexity status of some well-known multiobjective optimization problems and ask the question if these problems really are \(\mathbf {NP} \)-hard. It turns out, that most of them do not seem to be and for one we prove that if it is \(\mathbf {NP} \)-hard then this would imply \(\mathbf {P} = \mathbf {NP} \) under assumptions from the literature. We also reason why \(\mathbf {NP} \)-hardness might not be well suited for investigating the complexity status of intractable multiobjective optimization problems.

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 Automatically Configuring Multi-objective Local Search Using Multi-objective Optimisation
Nächstes Kapitel Angle-Based Preference Models in Multi-objective Optimization
Literatur
1.
Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press, Cambridge (2009)CrossRefMATH
2.
Beier, R., Röglin, H., Vöcking, B.: The smoothed number of Pareto optimal solutions in bicriteria integer optimization. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 53–67. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-72792-7_​5 CrossRef
3.
Bökler, F., Ehrgott, M., Morris, C., Mutzel, P.: Output-sensitive complexity for multiobjective combinatorial optimization. J. Multi-Criteria Decis. Anal. (2017, accepted)
4.
Bökler, F., Mutzel, P.: Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 288–299. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48350-3_​25 CrossRef
5.
Brunsch, T., Röglin, H.: Improved smoothed analysis of multiobjective optimization. In: ACM SToC. pp. 407–426 (2012)
6.
Galand, L., Ismaili, A., Perny, P., Spanjaard, O.: Bidirectional preference-based search for multiobjective state space graph problems. In: SoCS 2013 (2013)
7.
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences, 1st edn. W. H. Freeman & Co., New York (1979)MATH
8.
Guerriero, F., Musmanno, R.: Label correcting methods to solve multicriteria shortest path problems. J. Optim. Theory Appl. 111(3), 589–613 (2001)MathSciNetCrossRefMATH
9.
Hansen, P.: Bicriterion path problems. In: Fandel, G., Gal, T. (eds.) Multiple Criteria Decision Making Theory and Application. Lecture Notes in Economics and Mathematical Systems, vol. 177, pp. 109–127. Springer, New York (1979)CrossRef
10.
Horoba, C.: Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem. Evol. Comput. 18(3), 357–381 (2010)CrossRef
11.
12.
Mohamed, C., Bassem, J., Taicir, L.: A genetic algorithm to solve the bicriteria shortest path problem. Electr. Notes Discret. Math. 36, 851–858 (2010)CrossRefMATH
13.
Müller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.: Timetable information: models and algorithms. In: Geraets, F., Kroon, F., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Algorithmic Methods for Railway Optimization. LNCS, vol. 4359. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-74247-0_​3
14.
15.
Raith, A., Ehrgott, M.: A comparison of solution strategies for biobjective shortest path problems. Comput. Oper. Res. 36(4), 1299–1331 (2009)MathSciNetCrossRefMATH
16.
Sanders, P., Mandow, L.: Parallel label-setting multi-objective shortest path search. In: Parallel & Distributed Processing (IPDPS), pp. 215–224. IEEE (2013)
17.
Serafini, P.: Some considerations about computational complexity for multi-objective combinatorial problems. In: Jahn, J., Krabs, W. (eds.) Recent Advances and Historical Development of Vector Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 294, pp. 222–231. Springer, Heidelberg (1986). doi:10.​1007/​978-3-642-46618-2_​15 CrossRef
18.
Shekelyan, M., Jossé, G., Schubert, M.: Paretoprep: fast computation of path skyline queries. In: Advances in Spatial and Temporal Databases (2015)
19.
Shekelyan, M., Jossé, G., Schubert, M., Kriegel, H.-P.: Linear Path Skyline Computation in Bicriteria Networks. In: Bhowmick, S.S., Dyreson, C.E., Jensen, C.S., Lee, M.L., Muliantara, A., Thalheim, B. (eds.) DASFAA 2014. LNCS, vol. 8421, pp. 173–187. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-05810-8_​12 CrossRef
20.
Skriver, A.J.V.: A classification of bicriterion shortest path algorithms. Asia-Pac. J. Oper. Res. 17, 199–212 (2000)MathSciNetMATH
21.
Tarapata, Z.: Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms. Int. J. Appl. Math. Comput. Sci. 17(2), 269–287 (2007)MathSciNetCrossRefMATH
22.
Tsaggouris, G., Zaroliagis, C.D.: Multiobjective optimization: Improved FPTAS for shortest paths and non-linear objectives with applications. Algorithms and Computation 4288, 389–398 (2006)MathSciNetMATH
23.
Metadaten
Titel
The Multiobjective Shortest Path Problem Is NP-Hard, or Is It?
verfasst von
Fritz Bökler
Copyright-Jahr
2017
Buch
Evolutionary Multi-Criterion Optimization

Print ISBN: 978-3-319-54156-3

Electronic ISBN: 978-3-319-54157-0

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-54157-0_6

Premium Partner

    Bildnachweise