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}-\varepsilon$ approximation in $\tfrac{1}{\varepsilon} \cdot \mathrm{poly}(n,m)$ time. The main technical ingredient is a dynamic witness-allocation framework that certifies adaptive reductions throughout the allocation process.
From: Shengwei Zhou [view email]
[v1]
Mon, 17 Nov 2025 07:01:54 UTC (328 KB)
[v2]
Mon, 7 Sep 2026 03:21:03 UTC (81 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。