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

Abstract

We present a new algorithm that achieves a $\frac{7}{9}$-approximation for the \emph{maximin share (MMS)} allocation of indivisible goods under additive valuations, improving the current best ratio of $\frac{10}{13}$~\cite{conf/soda/HeidariKSS26}. 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{poly}(n,m)$ time. The main technical ingredient is a dynamic witness-allocation framework that certifies adaptive reductions throughout the allocation process.

We have fixed a bug in the previous version and largely rewrite the proof details