Show simple item record

Approximate tradeoffs on weighted labeled matroids

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGourvès, Laurent*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553		*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorTlilane, Lydia*
dc.date.accessioned2015-04-14T17:38:43Z
dc.date.available2015-04-14T17:38:43Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14942
dc.language.isoenen
dc.subjectMatroiden
dc.subjectBi-objectiveen
dc.subjectAdditive weighten
dc.subjectWeighted labeleden
dc.subjectApproximate solutionen
dc.subject.ddc003en
dc.titleApproximate tradeoffs on weighted labeled matroidsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider problems where a solution is evaluated with a couple. Each coordinate of this couple represents the utility of an agent. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for both agents. Then a natural aim is to find a tradeoff. We investigate tradeoff solutions with worst case guarantees for the agents. The focus is on discrete problems having a matroid structure and the utility of an agent is modeled with a function which is either additive or weighted labeled. We provide polynomial-time deterministic algorithms which achieve several guarantees and we prove that some guarantees are not possible to reach.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol184en
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages154-166en
dc.relation.isversionofdoi10.1016/j.dam.2014.11.005en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01508729*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
10.1.1.408.4785.pdf
Size:
125.6Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record