Show simple item record

dc.contributor.authorGourvès, Laurent
dc.contributor.authorMonnot, Jérôme
dc.date.accessioned2019-04-30T10:53:43Z
dc.date.available2019-04-30T10:53:43Z
dc.date.issued2017
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18869
dc.descriptionLecture Notes in Computer Science book series (LNCS, volume 10236)en
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectFair divisionen
dc.subjectMatroidsen
dc.subject.ddc005en
dc.titleApproximate Maximin Share Allocations in Matroidsen
dc.typeCommunication / Conférence
dc.description.abstractenThe maximin share guarantee is, in the context of allocating indivisible goods to a set of agents, a recent fairness criterion. A solution achieving a constant approximation of this guarantee always exists and can be computed in polynomial time. We extend the problem to the case where the goods collectively received by the agents satisfy a matroidal constraint. Polynomial approximation algorithms for this generalization are provided: a 1/2-approximation for any number of agents, a (1−ε)-approximation for two agents, and a (8/9−ε)-approximation for three agents. Apart from the extension to matroids, the (8/9−ε)-approximation for three agents improves on a (7/8−ε)-approximation by Amanatidis et al. (ICALP 2015).en
dc.identifier.citationpages310-321en
dc.relation.ispartoftitleAlgorithms and Complexity: 10th International Conference (CIAC 2017)en
dc.relation.ispartofeditorFotakis, Dimitris
dc.relation.ispartofeditorPagourtzis, Aris
dc.relation.ispartofeditorTh. Paschos, Vangelis
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2017
dc.relation.ispartofpages486en
dc.relation.ispartofurl10.1007/978-3-319-57586-5en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-319-57585-8en
dc.relation.conftitle10th International Conference (CIAC 2017)en
dc.relation.confdate2017-05
dc.relation.confcityAthensen
dc.relation.confcountryGreeceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-57586-5_26en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-28T10:48:47Z
hal.person.labIds989
hal.person.labIds989
hal.identifierhal-02115557*


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