Restricted existence and approximation algorithms for PMMS

DOI10.1142/S0129054122460066MaRDI QIDQ6955225zbMATH OpenFDO

Authors Xinru Guo, Sijia Dai, Guichen Gao, Ruikang Ma, Yicheng Xu, Li Ning, Jianping Fan

Publication date 23 July 2025

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054122460066

zbMATH Keywords

algorithmic mechanism designapproximationfair divisionpairwise maximin share

Mathematics Subject Classification ID

Mechanism design theory (91B03) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites work

• A discrete and bounded envy-free cake cutting protocol for any number of agents
• A Little Charity Guarantees Almost Envy-Freeness
• Almost envy-freeness with general valuations
• An improved approximation algorithm for maximin shares
• Approximating maximin share allocations
• Approximation Algorithms for Computing Maximin Share Allocations
• Fair enough: guaranteeing approximate maximin shares
• scientific article; zbMATH DE number 1234106 (Why is no real title available?)
• scientific article; zbMATH DE number 6850473 (Why is no real title available?)
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• One-space bounded algorithms for two-dimensional bin packing
• Online algorithms for 1-space bounded 2-dimensional bin packing and square packing
• Splitting necklaces
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9

This page was built for publication: Restricted existence and approximation algorithms for PMMS

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