General Framework for Metric Optimization Problems with Delay or with Deadlines
General Framework for Metric Optimization Problems with Delay or with Deadlines
复制标题
具有延迟或截止日期的度量优化问题的通用框架
DOI：
10.1109/focs.2019.00013
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Noam Touitou
中科院分区：
文献类型：
--
作者：
Y. Azar;Noam Touitou
在本文中，我们提出了一个框架，用于构建和分析具有截止日期或度量空间上的延迟的在线优化问题的算法。使用这个框架，我们提出了针对几个不同问题的算法。我们提出了一种 O(D^2) 竞争性确定性算法，用于在深度 D 的树上进行延迟的在线多级聚合，这是比 Bienkowski 等人的 O(D^42^D) 竞争性算法的指数改进。 (ESA '16)，其中唯一先前已知的改进是针对 Buchbinder 等人的最后期限的特殊情况。 （苏打水'17）。我们还提出了一种用于在线服务的 O(log^2n) 竞争随机算法，该算法在任何 n 点的一般度量空间上都有延迟，改进了 Azar 等人提出的 O(log^4n) 竞争算法。 （STOC '17）。此外，我们还提出了有期限的在线设施定位问题。在这个问题中，请求随着时间的推移到达度量空间，并且需要通过以一定成本暂时打开的设施来提供服务，直到截止日期。我们还考虑带有延迟的设施选址问题，其中期限被任意延迟函数取代。对于这些问题，我们提出了 O(log^2n) 竞争算法，其中 n 是度量空间中的点数。我们提出的算法框架包括算法设计技术以及算法分析技术。
In this paper, we present a framework used to construct and analyze algorithms for online optimization problems with deadlines or with delay over a metric space. Using this framework, we present algorithms for several different problems. We present an O(D^2) -competitive deterministic algorithm for online multilevel aggregation with delay on a tree of depth D, an exponential improvement over the O(D^42^D) -competitive algorithm of Bienkowski et al. (ESA '16), where the only previously-known improvement was for the special case of deadlines by Buchbinder et al. (SODA '17). We also present an O(log^2n) -competitive randomized algorithm for online service with delay over any general metric space of n points, improving upon the O(log^4n) -competitive algorithm by Azar et al. (STOC '17). In addition, we present the problem of online facility location with deadlines. In this problem, requests arrive over time in a metric space, and need to be served until their deadlines by facilities that are opened momentarily for some cost. We also consider the problem of facility location with delay, in which the deadlines are replaced with arbitrary delay functions. For those problems, we present O(log^2n) -competitive algorithms, with n the number of points in the metric space. The algorithmic framework we present includes techniques for the design of algorithms as well as techniques for their analysis.