A truthful constant approximation for maximizing the minimum load on related machines

DOI10.1016/j.tcs.2013.04.003zbMath1294.90025OpenAlexW2000865829MaRDI QIDQ388122

Rob van Stee, George Christodoulou, Annamária Kovács

Publication date: 19 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.04.003

zbMATH Keywords

schedulingapproximation algorithmsalgorithmic mechanism designmachine covering

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items

A Unified Approach to Truthful Scheduling on Related Machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing the minimum load for selfish agents
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Approximation schemes for scheduling and covering on unrelated machines
• The Santa Claus problem
• Truthful Approximation Schemes for Single-Parameter Agents
• A Robust PTAS for Machine Covering and Packing
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Optimal Auction Design
• On Two Dimensional Packing
• On Allocating Goods to Maximize Fairness
• MaxMin allocation via degree lower-bounded arborescences