Improving the Bounds on Approximating Weighted Maximin Share for Chores

arXiv:2610.15520v1 Announce Type: cross Abstract: We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be alpha-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most alpha times her weighted maximin share. We establish that every instance admits a 4.124234528-WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a 4.12424-WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to e. Together, our results substantially narrow the previously best-known gap of [2,12] established by Li et al.~ite{LWX26} to [e,4.12424].

Source: arXiv cs.AI | 2026-10-15