Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems
Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme (2012), Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems, in Solis-Oba, Roberto, Approximation and Online Algorithms 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers, Springer : Berlin Heidelberg, p. 233-246
Type
Communication / ConférenceDate
2012Conference title
9th International Workshop on Approximation and Online Algorithms, WAOA 2011Conference date
2011-09Conference city
SaarbrückenConference country
GermanyBook title
Approximation and Online Algorithms 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected PapersBook author
Solis-Oba, RobertoPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-29115-9
Pages
233-246
Metadata
Show full item recordAuthor(s)
Bazgan, CristinaLaboratoire 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 biobjective optimization problems with a given number of solutions. This task is relevant for two reasons: (i) Pareto sets are often computationally hard so approximation is a necessary tradeoff to allow polynomial time algorithms; (ii) limiting explicitly the size of the approximation allows the decision maker to control the expected accuracy of approximation and prevents him to be overwhelmed with too many alternatives. 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 Bisection, Max Partition, Max Set Splitting and Max Matching.Subjects / Keywords
tradeoff; Maximization Problems; Pareto set; ApproximationRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme (2013) Article accepté pour publication ou publié
-
Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny (2013) Article accepté pour publication ou publié
-
Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny (2012) Communication / Conférence
-
Bazgan, Cristina; Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny; Vanderpooten, Daniel (2012) Communication / Conférence
-
Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2012) Communication / Conférence