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

DOI10.1016/J.TCS.2013.04.003zbMATH Open1294.90025OpenAlexW2000865829MaRDI QIDQ388122FDOQ388122

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

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

Recommendations

• A unified approach to truthful scheduling on related machines
• A deterministic truthful PTAS for scheduling related machines
• scientific article; zbMATH DE number 6297764
• A unified approach to truthful scheduling on related machines
• STACS 2004

zbMATH Keywords

approximation algorithmsschedulingalgorithmic mechanism designmachine covering

Mathematics Subject Classification ID

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

Cites Work

• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Optimal Auction Design
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• The Santa Claus problem
• Title not available (Why is that?)
• Maximizing the minimum load for selfish agents
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Approximation schemes for scheduling and covering on unrelated machines
• Setting lower bounds on truthfulness (extended abstract)
• Truthful approximation schemes for single-parameter agents
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Robust PTAS for Machine Covering and Packing
• On Two Dimensional Packing
• Title not available (Why is that?)
• On allocating goods to maximize fairness
• MaxMin allocation via degree lower-bounded arborescences

Cited In (2)

• The cost of selfishness for maximizing the minimum load on uniformly related machines
• A unified approach to truthful scheduling on related machines

This page was built for publication: A truthful constant approximation for maximizing the minimum load on related machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q388122)