A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs
A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs
复制标题
DOI：
10.4230/lipics.approx-random.2015.96
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
N. Bansal;Anupam Gupta;Ravishankar Krishnaswamy;K. Pruhs;Kevin Schewior;C. Stein
中科院分区：
文献类型：
--
作者：
N. Bansal;Anupam Gupta;Ravishankar Krishnaswamy;K. Pruhs;Kevin Schewior;C. Stein
我们考虑在实际线路上设定的自然在线优化问题。每个整数时间在线算法的状态是真实线路上的位置。在每个整数时，凸功能将在线到达。作为回应，在线算法选择了一个新位置。在线算法为此响应支付的成本是移动的距离，以及最终目的地的功能值。然后，目标是最大程度地减少所有时间的总成本。激励的应用程序是权威数据中心的权利。我们为此问题提供了一种2竞争性算法。我们还提供了一种3竞争性的无内存算法，并表明这是确定性的无内存算法可以达到的最佳竞争比率。最后，我们证明这个在线问题比标准的滑雪租赁问题严格困难。
We consider a natural online optimization problem set on the real line. The state of the online algorithm at each integer time is a location on the real line. At each integer time, a convex function arrives online. In response, the online algorithm picks a new location. The cost paid by the online algorithm for this response is the distance moved plus the value of the function at the final destination. The objective is then to minimize the aggregate cost over all time. The motivating application is rightsizing power-proportional data centers. We give a 2-competitive algorithm for this problem. We also give a 3-competitive memoryless algorithm, and show that this is the best competitive ratio achievable by a deterministic memoryless algorithm. Finally we show that this online problem is strictly harder than the standard ski rental problem.