Show simple item record

Approximate Tradeoffs on Matroids

dc.contributor.authorGourvès, Laurent*
dc.contributor.authorMonnot, Jérôme*
dc.contributor.authorTlilane, Lydia*
dc.date.accessioned2013-02-05T17:16:32Z
dc.date.available2013-02-05T17:16:32Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/10955
dc.language.isoenen
dc.subjectTradeoff solutionsen
dc.subjectMatroidsen
dc.subject.ddc003en
dc.titleApproximate Tradeoffs on Matroidsen
dc.typeCommunication / Conférence
dc.description.abstractenWe consider problems where a solution is evaluated with a couple. Each coordinate of this couple represents an agent’s utility. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for both agents. Then, a natural aim is to find tradeoffs. We investigate tradeoff solutions with guarantees for the agents.The focus is on discrete problems having a matroid structure. We provide polynomial-time deterministic algorithms which achieve several guarantees and we prove that some guarantees are not possible to reach.en
dc.identifier.citationpages360-365en
dc.relation.ispartofseriestitleFrontiers in Artificial Intelligence and Applicationsen
dc.relation.ispartofseriesnumbervol 242en
dc.relation.ispartoftitleECAI 2012 Proceedingsen
dc.relation.ispartofeditorDe Raedt, Luc
dc.relation.ispartofeditorBessière, Christian
dc.relation.ispartofeditorDubois, Didier
dc.relation.ispartofeditorDoherty, Patrick
dc.relation.ispartofeditorFrasconi, Paolo
dc.relation.ispartofeditorHeintz, Fredrik
dc.relation.ispartofeditorLucas, Peter
dc.relation.ispartofpublnameIOS Press Booksen
dc.relation.ispartofdate2012
dc.relation.ispartofpages413en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-1-61499-097-0en
dc.relation.conftitleEuropean Conference on Artificial Intelligence ECAI 2012en
dc.relation.confdate2012-08
dc.relation.confcityMontpellieren
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.identifier.doi10.3233/978-1-61499-098-7-360en
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-01508731*


Files in this item

Thumbnail
Name:
Ecai_matroid.pdf
Size:
130.3Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record