Research map / Learning theory and algorithms / Fairness
Settling the Maximin Share Fairness for Scheduling among Groups of Machines
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Resolves the open problem of group maximin share (GMMS) fair scheduling of jobs among groups of unrelated machines with a 2-approximate LP-rounding algorithm and matching lower bound, and improves the identical-machine case to 4/3.
Problem
Fair allocation of indivisible jobs (chores) among groups of machines under group maximin share (GMMS) fairness, where each group's cost is its minimum makespan; the case of unrelated machines within groups was open.
Approach
Uses a linear-programming relaxation (generalizing Lenstra et al.) to build a fractional GMMS-respecting allocation, removes share cycles by exchanging fractional items, and rounds so each machine has at most one fractional item, yielding a 2-GMMS allocation; for identical machines, an ordered-instance bag-filling algorithm achieves 4/3.
Key results
- A polynomial-time algorithm computes a 2-GMMS allocation for groups of unrelated machines (heterogeneous setting).
- A hard instance shows no algorithm can beat (2 - 1/n)-GMMS, so the ratio 2 is asymptotically tight.
- For groups of identical machines, a 4/3-GMMS allocation exists, improving the prior 2-approximation of Li et al. (2023).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LP rounding to compute an allocation | Scheduling among groups of unrelated machines · Heterogeneous machines | GMMS approximation ratio: 2 | Helped |
| Improve the approximation ratio from 2 to 4/3 | Homogeneous-agent GMMS allocation · Homogeneous machines | GMMS approximation ratio: 2 -> 4 3 | Helped |
| Apply polynomial-time techniques to the 4/3 algorithm | Homogeneous-agent GMMS allocation · Homogeneous machines | GMMS approximation ratio: 4 3 -> 4 3 + ϵ | Hurt |
| Require an exact GMMS allocation | Group chore allocation · Chores, n ≥ 3 groups with one agent each | Exact GMMS allocation existence: n ≥ 3 | Hurt |
Surprising findings
- Exact GMMS allocations may not exist even when every group has a single agent, reducing to MMS chore allocation with additive costs.
Limitations
- Tight lower bound (2 - 1/n) holds only as the number of groups grows large; gap remains for small n.
- Best possible approximation for homogeneous setting is unknown.
- Only identical and unrelated machines are considered; related-machine case left open.
Experimental setup
Metrics: approximation ratio
Baselines: Li et al. 2023 2-GMMS algorithm for identical machines
Builds on: Li et al. 2023 group MMS framework Lenstra et al. 1990 LP rounding Barman & Krishnamurthy 2020
Closest papers by meaning
- Algorithms for Max-Min Share Fair Allocation of Indivisible Chores (AAAI 2017 · similarity 0.90)
- Fair Allocation of Indivisible Chores: Beyond Additive Costs (NeurIPS 2023 · similarity 0.89)
- Improved Maximin Share Approximations for Chores by Bin Packing (AAAI 2025 · similarity 0.88)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.85)
- The Price of Opportunity Fairness in Matroid Allocation Problems (NeurIPS 2025 · similarity 0.85)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.