Polynomial-time combinatorial algorithm for general max-min fair allocation

DOI10.1007/s00453-023-01105-3OpenAlexW4322494889MaRDI QIDQ6182677

Sheng-Yen Ko, Siu-Wing Cheng, Ho-Lin Chen, Wing-Kai Hon, Chung-Shou Liao

Publication date: 25 January 2024

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-023-01105-3

zbMATH Keywords

approximation algorithmshypergraph matchingmax-min allocation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fair resource allocation for different scenarios of demands
• Optimal semi-online preemptive algorithms for machine covering on two uniform machines
• Approximation algorithms for scheduling unrelated parallel machines
• A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem
• The exact LPT-bound for maximizing the minimum completion time
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Restricted max-min allocation: integrality gap and approximation algorithm
• Fair resource allocation: using welfare-based dominance constraints
• The Santa Claus problem
• Santa claus meets hypergraph matchings
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• A new approximation technique for resource‐allocation problems
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• Restricted Max-Min Fair Allocation
• A Tale of Santa Claus, Hypergraphs and Matroids
• On Allocating Goods to Maximize Fairness

This page was built for publication: Polynomial-time combinatorial algorithm for general max-min fair allocation