Name
Abstract | ||
|---|---|---|
The 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.tcs.2018.05.018 | Theoretical Computer Science |
Keywords | Field | DocType |
Approximation algorithms,Fair division,Matroids | Matroid,Discrete mathematics,Approximation algorithm,Minimax,Combinatorics,Fair division,Polynomial,Time complexity,Mathematics | Journal |
Volume | ISSN | Citations |
754 | 0304-3975 | 1 |
PageRank | References | Authors |
0.37 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Gourvès | 1 | 241 | 30.97 |
| Jérôme Monnot | 2 | 512 | 55.74 |