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

Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme

Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme (2013), Approximation with a fixed number of solutions of some multiobjective maximization problems, Journal of Discrete Algorithms, 22, p. 19-29. 10.1016/j.jda.2013.06.006

View/Open

waoa11max.pdf (152.1Kb)

Type

Article accepté pour publication ou publié

Date

2013

Journal name

Journal of Discrete Algorithms

Volume

Publisher

Elsevier

Pages

19-29

Publication identifier

10.1016/j.jda.2013.06.006

Metadata

Show full item record

Author(s)

Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]

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.

Subjects / Keywords

Submodular functions; Multiobjective maximization problems; Approximation; Bisection; Coverage; Matching