Output details
11 - Computer Science and Informatics
University of Liverpool
Return to search
Output 0 of 0 in the submission
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
1432-0541
Year of publication
2008
URL
-
Number of additional authors
2
Additional information
<12> Nisan and Ronen won the Goedel prize for their STOC 1999 paper, which initiated the field of Algorithmic Mechanism Design. They formulated a famous conjecture that concerns scheduling mechanisms. In this paper, we take a step towards the resolution of the problem, by giving an improvement on the lower bound. Our result for 3 machines is still the best known. Building on our construction, Koutsoupias and Vidali [Algorithmica 2013] extended the results to many machines. A preliminary version of this paper appeared in SODA 2007; it was not returned in RAE 2008.
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
-
