Document Open Access Logo

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.37.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Author Details

Anindya De
  • Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA
Sanjeev Khanna
  • Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA
Huan Li
  • Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA
Hesam Nikpey
  • Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA

Acknowledgements

We thank the anonymous reviewers for their valuable feedback. This work was supported in part by NSF awards CCF-1617851, CCF-1763514, CCF-1910534, CCF-1926872, and CCF-1934876.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ICALP.2020.37

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Discrete optimization
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Scheduling algorithms
Keywords
  • Efficient PTAS
  • Makespan Minimization
  • Scheduling
  • Stochastic Load Balancing
  • Poisson Distribution

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Yossi Azar, Gerhard J Woeginger, and Tal Yadid. Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1(1):55-66, 1998. Google Scholar
  2. Clive W Anderson, Stuart G Coles, and Jürg Hüsler. Maxima of poisson-like variables and related triangular arrays. The Annals of Applied Probability, pages 953-971, 1997. Google Scholar
  3. CW Anderson. Extreme value theory for a class of discrete distributions with applications to some stochastic processes. Journal of Applied Probability, 7(1):99-113, 1970. Google Scholar
  4. Keith M Briggs, Linlin Song, and Thomas Prellberg. A note on the distribution of the maximum of a set of poisson random variables. arXiv preprint, 2009. URL: http://arxiv.org/abs/0903.4373.
  5. Chandra Chekuri and Michael Bender. An efficient approximation algorithm for minimizing makespan on uniformly related machines. Journal of Algorithms, 41(2):212-224, 2001. Google Scholar
  6. Lin Chen, Klaus Jansen, and Guochuan Zhang. On the optimality of approximation schemes for the classical scheduling problem. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 657-668. SIAM, 2014. Google Scholar
  7. Fabián A Chudak and David B Shmoys. Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. Journal of Algorithms, 30(2):323-343, 1999. Google Scholar
  8. D Darling. On the supremum of a certain gaussian process. The Annals of Probability, pages 803-806, 1983. Google Scholar
  9. Ashish Goel and Piotr Indyk. Stochastic load balancing and related problems. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 579-586, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814632.
  10. R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Tech. J., pages 1563-1581, 1966. Google Scholar
  11. Anupam Gupta, Amit Kumar, Viswanath Nagarajan, and Xiangkun Shen. Stochastic load balancing on unrelated machines. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1274-1285. SIAM, 2018. Google Scholar
  12. Dorit S Hochbaum and David B Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM (JACM), 34(1):144-162, 1987. Google Scholar
  13. Hochbaum, Dorit S and Shmoys, David B. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM journal on computing, 17(3):539-551, 1988. Google Scholar
  14. Klaus Jansen. An EPTAS for scheduling jobs on uniform processors: Using an MILP relaxation with a constant number of integral variables. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, pages 562-573, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_47.
  15. Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the gap for makespan scheduling via sparsification techniques. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 72:1-72:13, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.72.
  16. Klaus Jansen and Lars Rohwedder. On integer programming and convolution. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 43:1-43:17, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.43.
  17. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415-440, 1987. URL: https://doi.org/10.1287/moor.12.3.415.
  18. Jon Kleinberg, Yuval Rabani, and Éva Tardos. Allocating bandwidth for bursty connections. SIAM Journal on Computing, 30(1):191-217, 2000. Google Scholar
  19. Hendrik W. Lenstra. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538-548, 1983. URL: https://doi.org/10.1287/moor.8.4.538.
  20. Jan Karel Lenstra, David B Shmoys, and Eva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming, 46(1-3):259-271, 1990. Google Scholar
  21. Michael Mitzenmacher and Eli Upfal. Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017. Google Scholar
  22. Marco Molinaro. Stochastic 𝓁_p load balancing and moment problems via the l-function method. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 343-354. SIAM, 2019. Google Scholar
  23. Herbert Robbins. A remark on stirling’s formula. The American mathematical monthly, 62(1):26-29, 1955. Google Scholar
  24. Michel Talagrand. Majorizing measures: the generic chaining. The Annals of Probability, 24(3):1049-1103, 1996. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact