An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs

Anindya De, Sanjeev Khanna, Huan Li +1

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-ap…