• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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érence
Date
2012
Conference title
9th International Workshop on Approximation and Online Algorithms, WAOA 2011
Conference date
2011-09
Conference city
Saarbrücken
Conference country
Germany
Book title
Approximation and Online Algorithms 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
Book author
Solis-Oba, Roberto
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-29115-9
Pages
233-246
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 cc
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; Approximation

Related items

Showing items related by title and author.

  • Thumbnail
    Approximation with a fixed number of solutions of some multiobjective maximization problems 
    Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme (2013) Article accepté pour publication ou publié
  • Thumbnail
    Single approximation for biobjective Max TSP 
    Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny (2013) Article accepté pour publication ou publié
  • Thumbnail
    Single Approximation for Biobjective Max TSP 
    Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny (2012) Communication / Conférence
  • Thumbnail
    Solutions équitables approchées pour divers problèmes d’optimisation combinatoire 
    Bazgan, Cristina; Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny; Vanderpooten, Daniel (2012) Communication / Conférence
  • Thumbnail
    Approximation polynomiale pour des problèmes de matroïdes bi-objectifs 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2012) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo