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.2017.51
URN: urn:nbn:de:0030-drops-78287
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7828/
Go to the corresponding LIPIcs Volume Portal

Im, Sungjin ; Moseley, Benjamin ; Pruhs, Kirk ; Stein, Clifford

Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing

pdf-format:
LIPIcs-ESA-2017-51.pdf (0.4 MB)

Abstract

We consider a setting where selfish agents want to schedule jobs on related machines. The agent submitting a job picks a server that minimizes a linear combination of the server price and the resulting response time for that job on the selected server. The manager's task is to maintain server prices to (approximately) optimize the maximum response time, which is a measure of social good. We show that the existence of a pricing scheme with certain competitiveness is equivalent to the existence of a monotone immediate-dispatch algorithm. Our main result is a monotone immediate-dispatch algorithm that is O(1)-competitive with respect to the maximum response time.

BibTeX - Entry

@InProceedings{im_et_al:LIPIcs:2017:7828,
  author =	{Sungjin Im and Benjamin Moseley and Kirk Pruhs and Clifford Stein},
  title =	{{Minimizing Maximum Flow Time on Related Machines via  Dynamic Posted Pricing}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{51:1--51:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7828},
  URN =		{urn:nbn:de:0030-drops-78287},
  doi =		{10.4230/LIPIcs.ESA.2017.51},
  annote =	{Keywords: Posted pricing scheme, online scheduling, related machines, maximum flow time, competitiveness analysis}
}

Keywords: Posted pricing scheme, online scheduling, related machines, maximum flow time, competitiveness analysis
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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