UNIVERSITÄTSBIBLIOTHEK

Connectedness of Efficient Solutions in Multiple Criteria Combinatorial Optimization

  • In multiple criteria optimization an important research topic is the topological structure of the set \( X_e \) of efficient solutions. Of major interest is the connectedness of \( X_e \), since it would allow the determination of \( X_e \) without considering non-efficient solutions in the process. We review general results on the subject,including the connectedness result for efficient solutions in multiple criteria linear programming. This result can be used to derive a definition of connectedness for discrete optimization problems. We present a counterexample to a previously stated result in this area, namely that the set of efficient solutions of the shortest path problem is connected. We will also show that connectedness does not hold for another important problem in discrete multiple criteria optimization: the spanning tree problem.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Matthias Ehrgott, Kathrin Klamroth
URN (Permalink):urn:nbn:de:hbz:386-kluedo-48443
Schriftenreihe (Bandnummer):Preprints (rote Reihe) des Fachbereich Mathematik (265)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):13.10.2017
Jahr der Veröffentlichung:1995
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):16.10.2017
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)