2026-07-22T10:56:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12444 2024-03-06T10:50:09Z ddc:004 open_access

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs De, Anindya Khanna, Sanjeev Li, Huan Nikpey, Hesam Efficient PTAS Makespan Minimization Scheduling Stochastic Load Balancing Poisson Distribution 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anindya De and Sanjeev Khanna and Huan Li and Hesam Nikpey 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.37 urn:nbn:de:0030-drops-124449 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.37 eng https://creativecommons.org/licenses/by/3.0/legalcode