Search Results

Documents authored by Taub, Tzahi


Document
Truthful Prompt Scheduling for Minimizing Sum of Completion Times

Authors: Alon Eden, Michal Feldman, Amos Fiat, and Tzahi Taub

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


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.

Cite as

Alon Eden, Michal Feldman, Amos Fiat, and Tzahi Taub. Truthful Prompt Scheduling for Minimizing Sum of Completion Times. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.ESA.2018.27,
  author =	{Eden, Alon and Feldman, Michal and Fiat, Amos and Taub, Tzahi},
  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 =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.27},
  URN =		{urn:nbn:de:0030-drops-94905},
  doi =		{10.4230/LIPIcs.ESA.2018.27},
  annote =	{Keywords: Scheduling, Mechanism design, Online algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail