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

Abstract: We present a new algorithm that achieves a (7/9)-approximation for the maximin share (MMS) allocation of indivisible goods under additive valuations, improving the current best ratio of 10/13 (Heidari et al., SODA 2026). Building on a new analytical framework, we further obtain an FPTAS that achieves a (7/9-\epsilon)-approximation in (poly(m,n)/\esilon)-time. Compared with prior work (Heidari et al., SODA 2026), our algorithm is substantially simpler.