Show simple item record

dc.contributor.authorGourvès, Laurent*
dc.contributor.authorMonnot, Jérôme*
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.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-01508729*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record