Show simple item record

dc.contributor.authorBazgan, Cristina*
dc.contributor.authorGourvès, Laurent*
dc.contributor.authorMonnot, Jérôme*
dc.date.accessioned2012-04-24T11:58:23Z
dc.date.available2012-04-24T11:58:23Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9033
dc.language.isoenen
dc.subjecttradeoff
dc.subjectMaximization Problems
dc.subjectPareto set
dc.subjectApproximation
dc.subject.ddc003en
dc.titleApproximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherInstitut Universitaire de France;France
dc.contributor.editoruniversityotherCNRS, UMR 7243;France
dc.description.abstractenWe 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.
dc.identifier.citationpages233-246
dc.relation.ispartoftitleApproximation and Online Algorithms 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
dc.relation.ispartofeditorSolis-Oba, Roberto
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2012
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-29115-9
dc.relation.conftitle9th International Workshop on Approximation and Online Algorithms, WAOA 2011
dc.relation.confdate2011-09
dc.relation.confcitySaarbrücken
dc.relation.confcountryGermany
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-05T15:27:50Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-01505591*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record