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

DOI10.1016/J.TCS.2013.04.003MaRDI QIDQ388122zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmsschedulingalgorithmic mechanism designmachine covering

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(2)

• A unified approach to truthful scheduling on related machines
• The cost of selfishness for maximizing the minimum load on uniformly 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)