DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.37

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs

Authors: Anindya De, Sanjeev Khanna, Huan Li, and Hesam Nikpey

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

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.

Cite as

Anindya De, Sanjeev Khanna, Huan Li, and Hesam Nikpey. An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.ICALP.2020.37,
  author =	{De, Anindya and Khanna, Sanjeev and Li, Huan and Nikpey, Hesam},
  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 =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.37},
  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}
}

Document

DOI: 10.4230/LIPIcs.ESA.2019.71

Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

Authors: Huan Li, He Sun, and Luca Zanetti

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract

We study spectral approaches for the MAX-2-LIN(k) problem, in which we are given a system of m linear equations of the form x_i - x_j is equivalent to c_{ij} mod k, and required to find an assignment to the n variables {x_i} that maximises the total number of satisfied equations. We consider Hermitian Laplacians related to this problem, and prove a Cheeger inequality that relates the smallest eigenvalue of a Hermitian Laplacian to the maximum number of satisfied equations of a MAX-2-LIN(k) instance I. We develop an O~(kn^2) time algorithm that, for any (1-epsilon)-satisfiable instance, produces an assignment satisfying a (1 - O(k)sqrt{epsilon})-fraction of equations. We also present a subquadratic-time algorithm that, when the graph associated with I is an expander, produces an assignment satisfying a (1- O(k^2)epsilon)-fraction of the equations. Our Cheeger inequality and first algorithm can be seen as generalisations of the Cheeger inequality and algorithm for MAX-CUT developed by Trevisan.

Cite as

Huan Li, He Sun, and Luca Zanetti. Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ESA.2019.71,
  author =	{Li, Huan and Sun, He and Zanetti, Luca},
  title =	{{Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.71},
  URN =		{urn:nbn:de:0030-drops-111926},
  doi =		{10.4230/LIPIcs.ESA.2019.71},
  annote =	{Keywords: Spectral methods, Hermitian Laplacians, the Max-2-Lin problem, Unique Games}
}

Search Results

Documents authored by Li, Huan

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs

Abstract

Cite as

Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message