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 algorithmsmatroidsfair division

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 863480 (Why is no real title available?)
• 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
• Some Abstract Pivot Algorithms

Cited in

(14)

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

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)