An Algorithmic Framework for Approximating Maximin Share Allocation of Chores

Understand

In this paper, we consider the problem of how to fairly dividing $m$ indivisible chores among $n$ agents.

• The fairness measure we considered here is the maximin share.
• The previous best known result is that there always exists a $\frac{4}{3}$ approximation maximin share allocation.
• With a novel algorithm, we can always find a $\frac{11}{9}$ approximation maximin share allocation for any instances.