← 研踪 PaperTrailarXiv:2611.07468 · v1
Polynomial-Time Approximate EFX for Chores via Flow and Matching
首次提交 2026-11-05 13:27
版本更新 2026-11-05 13:27
雷达观测 2026-11-06 12:09
摘要
We study approximate EFX allocations of indivisible chores under nonnegative additive costs. Exact EFX allocations need not exist in general. We develop a polynomial-time algorithm that computes a complete $(3+\varepsilon)$-EFX allocation for any rational $0<\varepsilon\leq1$, improving the previous approximation guarantee from a factor depending on the number of agents to a constant. The algorithm extends to EF$k$X, achieving a $(2+1/k+\varepsilon)$-approximation for every integer $k\geq1$. For instances with relatively few chores, the polynomial-time BRBI algorithm gives stronger guarantees. It finds exact EF$k$X allocations when $m\leq2kn$ and achieves a factor of at most $2-1/k$ when $m\le(3k-1)n$. In particular, $k=1$ and $m\leq2n$ give exact EFX. We further show that the approximation factor \(2+1/k\) is asymptotically tight for our main algorithm. We also construct a four-agent, ten-chore instance in which every complete allocation has EFX approximation factor at least $11/10$, improving upon the $20/19$ lower bound for submodular costs even under additive costs.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 13:27 · 最新观测版本
Polynomial-Time Approximate EFX for Chores via Flow and Matching
We study approximate EFX allocations of indivisible chores under nonnegative additive costs. Exact EFX allocations need not exist in general. We develop a polynomial-time algorithm that computes a complete $(3+\varepsilon)$-EFX allocation for any rational $0<\varepsilon\leq1$, improving the previous approximation guarantee from a factor depending on the number of agents to a constant. The algorithm extends to EF$k$X, achieving a $(2+1/k+\varepsilon)$-approximation for every integer $k\geq1$. For instances with relatively few chores, the polynomial-time BRBI algorithm gives stronger guarantees. It finds exact EF$k$X allocations when $m\leq2kn$ and achieves a factor of at most $2-1/k$ when $m\le(3k-1)n$. In particular, $k=1$ and $m\leq2n$ give exact EFX. We further show that the approximation factor \(2+1/k\) is asymptotically tight for our main algorithm. We also construct a four-agent, ten-chore instance in which every complete allocation has EFX approximation factor at least $11/10$, improving upon the $20/19$ lower bound for submodular costs even under additive costs.
查看此版本解读 →查看此版本原文 ↗