License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1314
URN: urn:nbn:de:0030-drops-13146
URL: https://drops.dagstuhl.de/opus/volltexte/2008/1314/
Go to the corresponding LIPIcs Volume Portal


Lu, Pinyan ; Yu, Changyuan

An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

pdf-format:
22011.LuPinyan.Paper.1314.pdf (0.2 MB)


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)


BibTeX - Entry

@InProceedings{lu_et_al:LIPIcs:2008:1314,
  author =	{Pinyan Lu and Changyuan Yu},
  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 =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1314},
  URN =		{urn:nbn:de:0030-drops-13146},
  doi =		{10.4230/LIPIcs.STACS.2008.1314},
  annote =	{Keywords: Truthful mechanism, scheduling}
}

Keywords: Truthful mechanism, scheduling
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI