arXiv：cs.AI· Trung Thanh Nguyen, Khaled Elbassioni, J\"{o}rg Rothe·· 10 小时前
加权最大最小份额分配家务的近似比上界改进至 4.12424
Improving the Bounds on Approximating Weighted Maximin Share for Chores
AI 导读
研究者在不可分家务分配问题中证明，任意权重和可加非负成本函数下，每个实例都存在 4.124234528-WMMS 公平分配。对于权重和成本为二进制有理数的实例，给出了在智能体数、家务数和输入编码长度上多项式时间的 4.12424-WMMS 分配算法。同时构造了一族最优 WMMS 近似因子收敛到 e 的实例，将此前已知的 [2,12] 区间缩小至 [e,4.12424]。
正文
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]$.
| Subjects: | Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.15520 [cs.GT] |
| (or arXiv:2610.15520v1 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2610.15520 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Trung Nguyen [view email]
[v1]
Sun, 11 Oct 2026 10:37:27 UTC (64 KB)
来源：arXiv：cs.AI · arxiv.org