Approximation with a fixed number of solutions of some multiobjective maximization problems

Thumbnail
View/Open
Date
2013
Dewey
Recherche opérationnelle
Sujet
Submodular functions; Multiobjective maximization problems; Approximation; Bisection; Coverage; Matching
Journal issue
Journal of Discrete Algorithms
Volume
22
Publication date
2013
Article pages
19-29
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.jda.2013.06.006
URI
https://basepub.dauphine.fr/handle/123456789/11560
Collections
Metadata
Show full item record
Author
Bazgan, Cristina
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gourvès, Laurent
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Abstract (EN)
We investigate the problem of approximating the Pareto set of some multiobjective optimization problems with a given number of solutions. Our purpose is to exploit general properties that many well studied problems satisfy. We derive existence and constructive approximation results for the biobjective versions of Max Submodular Symmetric Function (and special cases), Max Bisection, and Max Matching and also for the k-objective versions of Max Coverage, Heaviest Subgraph, Max Coloring of interval graphs.