LIPIcs.STACS.2008.1314.pdf
- Filesize: 172 kB
- 12 pages
Document
An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines
Authors
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
Cite AsGet BibTex
Pinyan Lu and Changyuan Yu. An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 527-538, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1314
https://doi.org/10.4230/LIPIcs.STACS.2008.1314
Abstract
We study the scheduling problem on unrelated machines in the
mechanism design setting. This problem was proposed and studied in
the seminal paper (Nisan and Ronen 1999), where they gave a
$1.75$-approximation randomized truthful mechanism for the case of
two machines. We improve this result by a $1.6737$-approximation
randomized truthful mechanism. We also generalize our result to a
$0.8368m$-approximation mechanism for task scheduling with $m$
machines, which improve the previous best upper bound of
$0.875m( Mu'alem and Schapira 2007)
Keywords
- Truthful mechanism
- scheduling
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads