An Algorithmic Framework for Approximating Maximin Share Allocation of Chores

Xin Huang, Pinyan Lu

2021 · 26 citations · 24 references

Concepts

Abstract

We consider the problem of fairly dividing m indivisible chores among n agents. The fairness measure we consider here is the maximin share. The previous best known result is that there always exists a 4/3-approximation maximin share allocation[3]. With our algorithm, we can always find a 11/9-approximation maximin share allocation for any instance. We also discuss how to improve the efficiency of the algorithm and its connection to the job scheduling problem. The full paper can be found at https://arxiv.org/abs/1907.04505.

References

24