1 Search Results for "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-dev.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}
}
  • Refine by Author
  • 1 Eden, Alon
  • 1 Feldman, Michal
  • 1 Fiat, Amos
  • 1 Taub, Tzahi

  • Refine by Classification
  • 1 Theory of computation → Algorithmic mechanism design
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 Mechanism design
  • 1 Online algorithms
  • 1 Scheduling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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