Nearly Linear-Time Approximation Schemes for Mixed Packing/Covering and Facility-Location Linear Programs
Nearly Linear-Time Approximation Schemes for Mixed Packing/Covering and Facility-Location Linear Programs
复制标题
混合填充/覆盖和设施位置线性程序的近线性时间近似方案
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
N. Young
中科院分区：
文献类型：
--
作者：
N. Young
我们描述了近线性时间近似算法明确给定的混合包装/覆盖和设施位置的线性规划。该算法计算$（1+ N）$-近似解的时间为O（N log（N）/ε ^2）$，其中$N$是约束矩阵中非零的个数。我们还描述了并行变量，时间为$O（ ext{polylog}/epsilon^4）$并且只需要近似线性的总功，$O（N ext{polylog} /epsilon^2）$。这些是这些问题的第一近似方案，具有近线性时间顺序实现或近线性工作多对数时间并行实现。
We describe nearly linear-time approximation algorithms for explicitly given mixed packing/covering and facility-location linear programs. The algorithms compute $(1+epsilon)$-approximate solutions in time $O(N log(N)/epsilon^2)$, where $N$ is the number of non-zeros in the constraint matrix. We also describe parallel variants taking time $O( ext{polylog}/epsilon^4)$ and requiring only near-linear total work, $O(N ext{polylog} /epsilon^2)$. These are the first approximation schemes for these problems that have near-linear-time sequential implementations or near-linear-work polylog-time parallel implementations.