UNIVERSITÄTSBIBLIOTHEK

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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Matthias Ehrgott
URN (Permalink):urn:nbn:de:hbz:386-kluedo-48507
Schriftenreihe (Bandnummer):Preprints (rote Reihe) des Fachbereich Mathematik (267)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):16.10.2017
Jahr der Veröffentlichung:1995
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):16.10.2017
Seitenzahl:19
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)