Approximate maximin share allocations in matroids

DOI10.1007/978-3-319-57586-5_26MaRDI QIDQ5283377zbMATH OpenOpenAlexFDO

Authors Laurent Gourvès, Jérôme Monnot

Publication date 21 July 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-57586-5_26

zbMATH Keywords

approximation algorithmsfair divisionmatroids

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)

Recommendations

• On maximin share allocations in matroids
• Approximation Algorithms for Computing Maximin Share Allocations
• Approximation algorithms for computing maximin share allocations
• Fair enough: guaranteeing approximate maximin shares
• An improved approximation algorithm for maximin shares

Cites work

• A Multiple Exchange Property for Bases
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• A protocol for cutting matroids like cakes
• An approximation algorithm for max-min fair allocation of indivisible goods
• An exchange theorem for bases of matroids
• Approximation algorithms for computing maximin share allocations
• Combinatorial optimization. Theory and algorithms.
• Comments on bases in dependence structures
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 863480 (Why is no real title available?)
• Some Abstract Pivot Algorithms

Cited in

(14)

• On maximin share allocations in matroids
• Approximate maximin shares for groups of agents
• An improved approximation algorithm for maximin shares
• Maximin share guarantee for goods with positive externalities
• Worst case compromises in matroids with applications to the allocation of indivisible goods
• Agreeable sets with matroidal constraints
• Fair allocation of indivisible goods: beyond additive valuations
• A protocol for cutting matroids like cakes
• Approximation algorithms for computing maximin share allocations
• Approximate tradeoffs on matroids
• Approximation Algorithms for Computing Maximin Share Allocations
• A Characterization of Undirected Graphs Admitting Optimal Cost Shares
• Near fairness in matroids
• On Fair Division under Heterogeneous Matroid Constraints

This page was built for publication: Approximate maximin share allocations in matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283377)