Output details
11 - Computer Science and Informatics
University of Leicester
Output title
A unified approach to truthful scheduling on related machines
Type
E - Conference contribution
DOI
-
Name of conference/published proceedings
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume number
-
Issue number
-
First page of article
1243
ISSN of proceedings
-
Year of publication
2013
URL
-
Number of additional authors
2
Additional information
<12>This paper completely solves a well-known open problem, namely the existence of polynomial-time approximation schemes for truthful scheduling - a fundamental question in algorithmic game theory. This closes a long line of research started in FOCS'01, with intermediate results appearing in STACS'04, STACS'05, ESA'05, J. Discr. Alg.'09, FOCS'08 and SODA'10. This last paper resolved one important case, but the algorithm was highly complex and involved a lengthy and technical case analysis, making it very hard to follow and develop further. We provide a streamlined and generalized proof, which applies to a large set of objective functions including the makespan.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
1
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
