论文标题
有效的PTA，用于与泊松工作的随机负载平衡
An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs
论文作者
论文摘要
当作业大小遵循泊松分布时，我们为随机负载平衡问题提供了第一个多项式时间近似方案（PTA）。这对由于Goel和Indyk引起的2个附属算法有所改善（FOCS'99）。此外，我们的近似方案是一个有效的PTA，其运行时间为$ 1/ε$，但在$ n $中几乎是线性的，其中$ n $是工作数，而$ε$是目标错误。以前，PTA（非高效）仅因遵守指数分布的工作而闻名（Goel和Indyk，Focs'99）。 我们的算法依赖于几种概率成分，包括一些（看似）对缩放的新结果以及可能具有独立兴趣的泊松随机变量的最大最大poisson随机变量的“聚焦效应”。
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.
