← 研踪 PaperTrailarXiv:2511.13056 · v3
A Strongly Polynomial-Time 7/9-Approximation Algorithm for Maximin Share Allocations
首次提交 2025-11-17 15:01
版本更新 2026-11-05 10:32
雷达观测 2026-11-06 11:06
摘要
We study maximin share (MMS) allocations of indivisible goods under nonnegative additive valuations. We give a strongly polynomial-time algorithm that allocates to every agent a bundle worth at least $7/9$ of her MMS, improving the previous $10/13$ guarantee of Heidari et al. (SODA 2026). Our analysis uses a dynamic witness-allocation framework that tracks the remaining goods from each agent's perspective throughout the allocation process. We obtain the computational result by iteratively refining upper bounds on MMS values, using only polynomially many runs of the allocation algorithm. Finally, we formalize and verify our main results in Lean 4.
作者备注：We have improved our result to a polynomial-time algorithm and reorganized the proof to be more structured
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-05 10:32 · 最新观测版本
A Strongly Polynomial-Time 7/9-Approximation Algorithm for Maximin Share Allocations
We study maximin share (MMS) allocations of indivisible goods under nonnegative additive valuations. We give a strongly polynomial-time algorithm that allocates to every agent a bundle worth at least $7/9$ of her MMS, improving the previous $10/13$ guarantee of Heidari et al. (SODA 2026). Our analysis uses a dynamic witness-allocation framework that tracks the remaining goods from each agent's perspective throughout the allocation process. We obtain the computational result by iteratively refining upper bounds on MMS values, using only polynomially many runs of the allocation algorithm. Finally, we formalize and verify our main results in Lean 4.
查看此版本解读 →查看此版本原文 ↗