Show simple item record

On maximin share allocations in 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
dc.date.accessioned2019-07-16T10:50:09Z
dc.date.available2019-07-16T10:50:09Z
dc.date.issued2019
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19244
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectFair divisionen
dc.subjectMatroidsen
dc.subject.ddc005en
dc.titleOn maximin share allocations in matroidsen
dc.typeArticle accepté pour publication ou publié
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). Some special cases are also presented and some extensions of the model are discussed.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol754en
dc.relation.isversionofjnldate2019-01
dc.relation.isversionofjnlpages50-64en
dc.relation.isversionofdoi10.1016/j.tcs.2018.05.018en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-07-16T10:42:47Z
hal.identifierhal-02184996*
hal.version1*
hal.author.functionaut
hal.author.functionaut


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