An FPTAS for 7/9-Approximation to Maximin Share Allocations

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}-\epsilon$ approximation in $\frac{1}{\epsilon }\cdot \mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n,m)$ time. Compared with prior work (Heidari et al., SODA 2026), our algorithm is substantially simpler.