• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >Solving Optimization Problems with Diseconomies of Scale via Decoupling
【24h】

Solving Optimization Problems with Diseconomies of Scale via Decoupling

机译：通过解耦解决规模不经济的优化问题

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 xq, 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 Aq, where Aq 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 ||Σn i=1 Xi||q ≤ Cq ||Σn i=1 Yi||q, where Xi are independent nonnegative random variables, Yi are possibly dependent nonnegative random variable, and each Yi has the same distribution as Xi. 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 Cq = Aq1/q.
机译：我们提出了一种解决规模不经济的优化问题的新框架。在此类问题中，我们的目标是最大程度地减少用于执行特定任务的资源成本。当xq，q≥1时，资源成本以所使用的资源数量x超线性增长。我们针对此类问题定义了一种新颖的线性规划松弛，然后证明了松弛的积分间隙为Aq，其中Aq是参数为1的Poisson随机变量的q矩。最小能量效率路由，最小度平衡生成树，无关并行机上的负载平衡以及具有完成时间非线性函数的无关并行机调度。我们的分析依赖于非负随机变量的解耦不等式。不等式说明||Σni = 1 Xi || q≤Cq ||Σni = 1 Yi || q，其中Xi是独立的非负随机变量，Yi可能是从属非负随机变量，并且每个Yi具有相同的分布作为Xi。 1990年，de laPeña证明了不等式。但是，最优常数Cq未知。我们证明最佳常数为Cq = Aq1 / q。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号