On maximin share allocations in matroids

DOI10.1016/j.tcs.2018.05.018zbMath1407.68547OpenAlexW2803597015WikidataQ129824788 ScholiaQ129824788MaRDI QIDQ1628590

Jérôme Monnot, Laurent Gourvès

Publication date: 4 December 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.05.018

zbMATH Keywords

matroidsfair divisionapproximation algorithms

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items

A tight negative example for MMS fair allocations, Ordinal Maximin Share Approximation for Goods, On Fair Division under Heterogeneous Matroid Constraints, Fair division of indivisible goods: recent progress and open questions, An improved approximation algorithm for maximin shares, Local fairness in hedonic games via individual threshold coalitions, The Price of Connectivity in Fair Division

Cites Work

• Unnamed Item
• Unnamed Item
• Partitioning general probability measures
• Greedoids
• Equitable distribution of indivisible objects
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• An exchange theorem for bases of matroids
• Worst case compromises in matroids with applications to the allocation of indivisible goods
• A Protocol for Cutting Matroids Like Cakes
• Approximation Algorithms for Computing Maximin Share Allocations
• Some Abstract Pivot Algorithms
• Approximate Maximin Share Allocations in Matroids
• An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
• Comments on bases in dependence structures
• A Multiple Exchange Property for Bases
• Combinatorial optimization. Theory and algorithms.