DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2008.1314

An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

Authors: Pinyan Lu and Changyuan Yu

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

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)

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.STACS.2008.1314,
  author =	{Lu, Pinyan and Yu, Changyuan},
  title =	{{An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{527--538},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1314},
  URN =		{urn:nbn:de:0030-drops-13146},
  doi =		{10.4230/LIPIcs.STACS.2008.1314},
  annote =	{Keywords: Truthful mechanism, scheduling}
}

Search Results

Documents authored by Yu, Changyuan

An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

Abstract

Cite as

Thanks for your feedback!

Could not send message