Output details
11 - Computer Science and Informatics
University of Oxford
Article title
A Lower Bound for Scheduling Mechanisms
Type
D - Journal article
Title of journal
Algorithmica
Article number
-
Volume number
55
Issue number
4
First page of article
729
ISSN of journal
0178-4617
Year of publication
2009
Number of additional authors
2
Additional information
<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.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
9
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
