{"ID":2840421,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.13056","arxiv_id":"2511.13056","title":"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 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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2511.13056","url_pdf":"https://arxiv.org/pdf/2511.13056v1","authors":"[\"Xin Huang\",\"Shengwei Zhou\"]","published":"2025-11-17T07:01:54Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.DS\"]","methods":"[]","has_code":false}