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

Thumbnail
Ouvrir
Date
2013
Indexation documentaire
Recherche opérationnelle
Subject
Submodular functions; Multiobjective maximization problems; Approximation; Bisection; Coverage; Matching
Nom de la revue
Journal of Discrete Algorithms
Volume
22
Date de publication
2013
Pages article
19-29
Nom de l'éditeur
Elsevier
DOI
http://dx.doi.org/10.1016/j.jda.2013.06.006
URI
https://basepub.dauphine.fr/handle/123456789/11560
Collections
Métadonnées
Afficher la notice complète
Auteur
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é
Résumé en anglais
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.