An FPTAS for 7/9-Approximation to Maximin Share Allocations
By: Xin Huang, Shengwei Zhou
Potential Business Impact:
Fairly divides items when people want different things.
We present a new algorithm that achieves a $\frac{7}{9}$-approximation for the maximin share (MMS) allocation of indivisible goods under additive valuations, improving the current best ratio of $\frac{10}{13}$ (Heidari et al., SODA 2026). Building on a new analytical framework, we further obtain an FPTAS that achieves a $\frac{7}{9}-\varepsilon$ approximation in $\tfrac{1}{\varepsilon} \cdot \mathrm{poly}(n,m)$ time. Compared with prior work (Heidari et al., SODA 2026), our algorithm is substantially simpler.
Similar Papers
Improved Maximin Share Guarantee for Additive Valuations
CS and Game Theory
Divides items fairly among people better.
Improved MMS Approximations for Few Agent Types
CS and Game Theory
Divides items fairly when people have similar tastes.
Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem
CS and Game Theory
Divides things fairly when people want different amounts.