Settling the Maximin Share Fairness for Scheduling among Groups of Machines

We study the fair scheduling of jobs among groups of (unrelated) machines and focus on the maximin share (MMS) fairness at the group level. The problem was first introduced by Li et al. [NeurIPS 2023], where each group consists of a number of identical machines (or identical up to different speeds), and the cost of a group is determined by the minimum makespan on completing all jobs assigned to it. It is left as an open problem when the machines within each group are unrelated. In this paper, we first resolve this problem and design a polynomial-time algorithm that computes a 2-approximate MMS allocation via linear programming techniques. We complement this result with a hard instance, showing that no algorithm can be better than $(2-\frac{1}{n})$-approximate MMS, where $n$ is the number of machines. Thus the approximation ratio 2 is asymptotically tight. When the groups consist of identical machines, we improve the approximation ratio to $\frac{4}{3}$.

The fair scheduling of jobs among groups of (unrelated) machines is studied in the paper and the maximin share at the group level is considered. Our paper uncovers many open problems and further directions.We show that no algorithm can be better than $(2-\frac{1}{n})$-approximate MMS, where $n$ is the number of machines and a 2-approximate MMS allocation can be computed in polynomial time via linear programming techniques.When the groups consist of identical machines, we improve the approximation ratio to $\frac{4}{3}$.