Preprint
Nov 2026
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 guara...
G. Qin, Qi-Zhi Fang, Min-Ming Li et al.
· 0 citations