Computer Science – Computer Science and Game Theory
Scientific paper
2009-07-17
Computer Science
Computer Science and Game Theory
Scientific paper
Scheduling on related machines ($Q||C_{\max}$) is one of the most important problems in the field of Algorithmic Mechanism Design. Each machine is controlled by a selfish agent and her valuation can be expressed via a single parameter, her {\em speed}. In contrast to other similar problems, Archer and Tardos \cite{AT01} showed that an algorithm that minimizes the makespan can be truthfully implemented, although in exponential time. On the other hand, if we leave out the game-theoretic issues, the complexity of the problem has been completely settled -- the problem is strongly NP-hard, while there exists a PTAS \cite{HS88,ES04}. This problem is the most well studied in single-parameter algorithmic mechanism design. It gives an excellent ground to explore the boundary between truthfulness and efficient computation. Since the work of Archer and Tardos, quite a lot of deterministic and randomized mechanisms have been suggested. Recently, a breakthrough result \cite{DDDR08} showed that a randomized truthful PTAS exists. On the other hand, for the deterministic case, the best known approximation factor is 2.8 \cite{Kov05,Kov07}. It has been a major open question whether there exists a deterministic truthful PTAS, or whether truthfulness has an essential, negative impact on the computational complexity of the problem. In this paper we give a definitive answer to this important question by providing a truthful {\em deterministic} PTAS.
Christodoulou George
Kovacs Annamaria
No associations
LandOfFree
A deterministic truthful PTAS for scheduling related machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A deterministic truthful PTAS for scheduling related machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A deterministic truthful PTAS for scheduling related machines will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-110767