A Deterministic Truthful PTAS for Scheduling Related Machines

DOI10.1137/120866038zbMath1290.68055arXiv0907.3068OpenAlexW2036744632MaRDI QIDQ2862203

George Christodoulou, Annamária Kovács

Publication date: 14 November 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0907.3068

zbMATH Keywords

algorithmic mechanism designalgorithmic game theoryrelated machine schedulingtruthful scheduling mechanisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Deterministic scheduling theory in operations research (90B35) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25)

Related Items (10)

The VCG Mechanism for Bayesian Scheduling ⋮ Setting lower bounds on truthfulness ⋮ Approximation guarantee of OSP mechanisms: the case of machine scheduling and facility location ⋮ Well-behaved online load balancing against strategic jobs ⋮ Truthful mechanism design via correlated tree rounding ⋮ No truthful mechanism can be better than \(n\) approximate for two natural problems ⋮ A Unified Approach to Truthful Scheduling on Related Machines ⋮ A new lower bound for deterministic truthful scheduling ⋮ Bribeproof Mechanisms for Two-Values Domains ⋮ Fair by design: multidimensional envy-free mechanisms

This page was built for publication: A Deterministic Truthful PTAS for Scheduling Related Machines