# Improving the Bounds on Approximating Weighted Maximin Share for Chores

arXiv: https://arxiv.org/abs/2610.15520 · HTML: https://mlsanity.com/paper/2610.15520/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 11 Oct 2026.

## Builds on (most cited first, 11 of 11)

- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [Fair Allocation of Indivisible Goods: Improvement and Generalization](https://mlsanity.com/paper/1704.00222/) (2017)
- [Approximation Algorithms for Computing Maximin Share Allocations](https://mlsanity.com/paper/1503.00941/) (2015)
- [An Improved Approximation Algorithm for Maximin Shares](https://mlsanity.com/paper/1903.00029/) (2019)
- [Approximation Algorithms for Maximin Fair Division](https://mlsanity.com/paper/1703.01851/) (2017)
- [Breaking the 3/4 Barrier for Approximate Maximin Share](https://mlsanity.com/paper/2307.07304/) (2023)
- [Fair Allocation of Indivisible Goods to Asymmetric Agents](https://mlsanity.com/paper/1703.01649/) (2017)
- [Simplification and Improvement of MMS Approximation](https://mlsanity.com/paper/2303.16788/) (2023)
- [Weighted Maxmin Fair Share Allocation of Indivisible Chores](https://mlsanity.com/paper/1906.07602/) (2019)
- [Constant Weighted Maximin Share Approximations for Chores](https://mlsanity.com/paper/2510.06581/) (2025)
- [Fair Assignment of Indivisible Chores to Asymmetric Agents](https://mlsanity.com/paper/2510.10698/) (2025)

## Abstract (arXiv)

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 α-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most α 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.~citeLWX26 to [e,4.12424].