• search hit 2 of 4
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

Share in Twitter Search Google Scholar
Author:Matthias Ehrgott
URN (permanent link):urn:nbn:de:hbz:386-kluedo-48507
Serie (Series number):Preprints (rote Reihe) des Fachbereich Mathematik (267)
Document Type:Report
Language of publication:English
Publication Date:2017/10/16
Year of Publication:1995
Publishing Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2017/10/16
Number of page:19
Faculties / Organisational entities: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)