ICS Theory Group

ICS 269, Fall 2004: Theory Seminar

12 Nov 2004:
Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines
Authors: Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Pino Persiano
Speaker: Matthew Ba Nguyen

From: Proceedings 21st International Symposium on Theoretical Aspects of Computer Science, 2004.

The authors consider the problem of scheduling jobs on parallel related machines owned by selfish agents. They present a family of algorithms that yield a (4+e)-approximation that incentivizes each selfish agent to report the actual speed of his or her machine -- i.e., each agent will maximize his or her own profit by reporting their actual speed.