• search hit 9 of 32
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Matthias Ehrgott
URN:urn:nbn:de:hbz:386-kluedo-48507
Series (Serial Number):Preprints (rote Reihe) des Fachbereich Mathematik (267)
Document Type:Report
Language of publication:English
Date of Publication (online):2017/10/16
Year of first Publication:1995
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2017/10/16
Page Number:19
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)