License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.27
URN: urn:nbn:de:0030-drops-94905
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9490/
Go to the corresponding LIPIcs Volume Portal

Eden, Alon ; Feldman, Michal ; Fiat, Amos ; Taub, Tzahi

Truthful Prompt Scheduling for Minimizing Sum of Completion Times

pdf-format:
LIPIcs-ESA-2018-27.pdf (0.6 MB)

Abstract

We give a prompt online mechanism for minimizing the sum of [weighted] completion times. This is the first prompt online algorithm for the problem. When such jobs are strategic agents, delaying scheduling decisions makes little sense. Moreover, the mechanism has a particularly simple form of an anonymous menu of options.

BibTeX - Entry

@InProceedings{eden_et_al:LIPIcs:2018:9490,
  author =	{Alon Eden and Michal Feldman and Amos Fiat and Tzahi Taub},
  title =	{{Truthful Prompt Scheduling for Minimizing Sum of Completion Times}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9490},
  URN =		{urn:nbn:de:0030-drops-94905},
  doi =		{10.4230/LIPIcs.ESA.2018.27},
  annote =	{Keywords: Scheduling, Mechanism design, Online algorithms}
}

Keywords: Scheduling, Mechanism design, Online algorithms
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

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