Research map / Learning theory and algorithms / Submodular and game algorithms
Algorithms for Max-Min Share Fair Allocation of Indivisible Chores
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SCHED heuristic (LPT bounds + ILP scheduling) instead of greedy round-robin | optimal MmS computation · Random chores instances, N in {2,4,8} | relative gap from optimal MmS ratio: SCHED max average deviation 1.64% | Helped |
| increase number of agents from 2 to 8 | optimal MmS ratio · Random chores instances | optimal MmS ratio: 0.82-0.67 (2 agents) -> 0.34-0.23 (8 agents) | Hurt |
| increase agents from 8 to 128 | SCHED worst-case gap · Random chores instances | maximum worst-case gap: 11.28% -> 11.92% | No clear effect |
Closest papers by meaning
- Improved Maximin Share Approximations for Chores by Bin Packing (AAAI 2025 · similarity 0.93)
- Settling the Maximin Share Fairness for Scheduling among Groups of Machines (ICML 2025 · similarity 0.90)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.90)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.89)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.89)
- Fair Allocation of Items in Multiple Regions (AAAI 2024 · similarity 0.88)
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.