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.ICALP.2020.37
URN: urn:nbn:de:0030-drops-124449
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12444/
Go to the corresponding LIPIcs Volume Portal

De, Anindya ; Khanna, Sanjeev ; Li, Huan ; Nikpey, Hesam

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs

pdf-format:
LIPIcs-ICALP-2020-37.pdf (0.6 MB)

Abstract

We give the first polynomial-time approximation scheme (PTAS) for the stochastic load balancing problem when the job sizes follow Poisson distributions. This improves upon the 2-approximation algorithm due to Goel and Indyk (FOCS'99). Moreover, our approximation scheme is an efficient PTAS that has a running time double exponential in 1/ε but nearly-linear in n, where n is the number of jobs and ε is the target error. Previously, a PTAS (not efficient) was only known for jobs that obey exponential distributions (Goel and Indyk, FOCS'99).
Our algorithm relies on several probabilistic ingredients including some (seemingly) new results on scaling and the so-called "focusing effect" of maximum of Poisson random variables which might be of independent interest.

BibTeX - Entry

@InProceedings{de_et_al:LIPIcs:2020:12444,
  author =	{Anindya De and Sanjeev Khanna and Huan Li and Hesam Nikpey},
  title =	{{An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12444},
  URN =		{urn:nbn:de:0030-drops-124449},
  doi =		{10.4230/LIPIcs.ICALP.2020.37},
  annote =	{Keywords: Efficient PTAS, Makespan Minimization, Scheduling, Stochastic Load Balancing, Poisson Distribution}
}

Keywords: Efficient PTAS, Makespan Minimization, Scheduling, Stochastic Load Balancing, Poisson Distribution
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

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