Solving Optimization Problems with Diseconomies of Scale via Decoupling
Solving Optimization Problems with Diseconomies of Scale via Decoupling
复制标题
通过解耦解决规模不经济的优化问题
DOI：
10.1145/3266140
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Sviridenko
中科院分区：
文献类型：
--
作者：
K. Makarychev;M. Sviridenko
我们提出了一个新的框架来解决规模不经济的优化问题。在这样的问题中，我们的目标是最小化用于执行特定任务的资源成本。资源成本随着使用的资源量x超线性增长，x<sup>q</sup>，q ≥ 1。我们定义了一个新的线性规划松弛这样的问题，然后证明了松弛的完整性差距是<sub>Aq</sub>，其中<sub>Aq</sub>是参数为1的泊松随机变量的q阶矩。使用我们的框架，我们得到的近似算法的最低能效路由，最小度平衡生成树，负载平衡不相关的并行机，和不相关的并行机调度与非线性函数的完成时间问题。我们的分析依赖于非负随机变量的解耦不等式。不等式指出，||n <sub>=1</sub><sup>n</sup> X <sub>i</sub>||<sub>q</sub> ≤ Cq|| Yi <sub>=1</sub><sup>n</sup> Y <sub>i</sub>||<sub>其中</sub>Xi为独立非负随机变量，Yi为可能相依非负随机变量，且每个<sub>Yi</sub>与Xi具有相同的分布<sub></sub>。1990年，de la Pen Penda证明了这个不等式。然而，最佳常数Cq未知。我们证明了最佳常数是<sub>Cq</sub>=<sub>Aq</sub><sup>1/q</sup>。
We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly, as x<sup>q</sup>, q ≥ 1, with the amount x of resources used. We define a novel linear programming relaxation for such problems, and then show that the integrality gap of the relaxation is A<sub>q</sub>, where A<sub>q</sub> is the q-th moment of the Poisson random variable with parameter 1. Using our framework, we obtain approximation algorithms for the Minimum Energy Efficient Routing, Minimum Degree Balanced Spanning Tree, Load Balancing on Unrelated Parallel Machines, and Unrelated Parallel Machine Scheduling with Nonlinear Functions of Completion Times problems. Our analysis relies on the decoupling inequality for nonnegative random variables. The inequality states that ||Σ<sub>i=1</sub><sup>n</sup>X<sub>i</sub>||<sub>q</sub> ≤ Cq ||Σ<sub>i=1</sub><sup>n</sup> Y<sub>i</sub>||<sub>q</sub>, where Xi are independent nonnegative random variables, Yi are possibly dependent nonnegative random variable, and each Y<sub>i</sub> has the same distribution as X<sub>i</sub>. The inequality was proved by de la Peña in 1990. However, the optimal constant Cq was not known. We show that the optimal constant is C<sub>q</sub> = A<sub>q</sub><sup>1/q</sup>.