Output details
11 - Computer Science and Informatics
University of Oxford
A Lower Bound for Scheduling Mechanisms
<12>
The most important open problem in algorithmic mechanism design is the approximation of scheduling unrelated machines. The problem was first studied in the seminal paper of Nisan and Ronen in 1999, in which they showed that the deterministic approximation ratio is between 2 and n, the number of machines. Despite the importance of the problem, there was no progress until this work improved the lower bound to 2.41. Subsequently, the second and third author improved the bound to 2.61, which remains even today the best result for this central problem.
A preliminary version of this paper appeared in the conference SODA 2007. It was not submitted to RAE2008.