2026-10-15 · ArXiv
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.~\cite{LWX26} to $[e,4.12424]$.
原文链接：https://arxiv.org/abs/2610.15520
查看更多资讯请见 AI 行业资讯。