On Matroids with Multiple Objectives
- In this paper we investigate two optimization problems for matroids with multiple objective functions, namely finding the pareto set and the max-ordering problem which conists in finding a basis such that the largest objective value is minimal. We prove that the decision versions of both problems are NP-complete. A solution procedure for the max-ordering problem is presented and a result on the relation of the solution sets of the two problems is given. The main results are a characterization of pareto bases by a basis exchange property and finally a connectivity result for proper pareto solutions.
Verfasser*innenangaben: | Matthias Ehrgott |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-48507 |
Schriftenreihe (Bandnummer): | Preprints (rote Reihe) des Fachbereich Mathematik (267) |
Dokumentart: | Bericht |
Sprache der Veröffentlichung: | Englisch |
Datum der Veröffentlichung (online): | 16.10.2017 |
Jahr der Erstveröffentlichung: | 1995 |
Veröffentlichende Institution: | Technische Universität Kaiserslautern |
Datum der Publikation (Server): | 16.10.2017 |
Seitenzahl: | 19 |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - 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) |