Improved online algorithms for the sorting buffer problem on line metrics
Improved online algorithms for the sorting buffer problem on line metrics
复制标题
改进了在线度量排序缓冲区问题的在线算法
DOI：
10.1145/1644015.1644030
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Segev
中科院分区：
文献类型：
--
作者：
Iftah Gamzu;D. Segev
排序缓冲区问题的一个实例由一个度量空间和一个服务器组成，该服务器配备了一个有限容量的缓冲区，能够容纳有限数量的请求。输入的另一个组成部分是一个在线请求序列，每个请求都以给定度量空间中的目的地为特征;每当请求到达时，它必须存储在排序缓冲区中。在任何时间点，可以通过将当前挂起的请求从缓冲区中取出并将服务器移动到其相应的目的地来处理该请求。其目标是以最小化服务器行进的总距离的方式来服务所有输入请求。
在这篇文章中，我们把注意力集中在问题的例子中，其中的基本度量是均匀间隔线度量或连续线度量。我们的主要发现可以简要地总结如下。
(1)我们提出了一个确定性的O（log n）-竞争算法的n点均匀间隔线度量。这个结果改进了Khandekar和Pandit [2006 b]的随机O（log 2 n）-竞争算法。它还驳斥了他们的猜想，指出确定性策略不太可能获得非平凡的竞争比。
(2)我们设计了一个确定性O（log N log N）的竞争算法连续线度量，其中N表示的输入序列的长度。在这方面，我们介绍了一种新的离散化技术的独立利益。
(3)通过证明任何确定性算法的竞争比至少为2 + 3/3 <$2.154，我们建立了均匀间隔情况下的第一个非平凡下界。这一结果在一定程度上解决了Khandekar和Pandit [2006 b]提出的一个悬而未决的问题，他们提出了获得可实现竞争比下限的任务，作为未来研究的基本目标。
An instance of the sorting buffer problem consists of a metric space and a server, equipped with a finite-capacity buffer capable of holding a limited number of requests. An additional ingredient of the input is an online sequence of requests, each of which is characterized by a destination in the given metric space; whenever a request arrives, it must be stored in the sorting buffer. At any point in time, a currently pending request can be served by drawing it out of the buffer and moving the server to its corresponding destination. The objective is to serve all input requests in a way that minimizes the total distance traveled by the server.
In this article, we focus our attention on instances of the problem in which the underlying metric is either an evenly-spaced line metric or a continuous line metric. Our main findings can be briefly summarized as follows.
(1) We present a deterministic O(log n)-competitive algorithm for n-point evenly-spaced line metrics. This result improves on a randomized O(log2 n)-competitive algorithm due to Khandekar and Pandit [2006b]. It also refutes their conjecture, stating that a deterministic strategy is unlikely to obtain a nontrivial competitive ratio.
(2) We devise a deterministic O(log N log log N)-competitive algorithm for continuous line metrics, where N denotes the length of the input sequence. In this context, we introduce a novel discretization technique of independent interest.
(3) We establish the first nontrivial lower bound for the evenly-spaced case, by proving that the competitive ratio of any deterministic algorithm is at least 2 + &sqrt;3/&sqrt;3 ≈ 2.154. This result settles, to some extent, an open question due to Khandekar and Pandit [2006b], who posed the task of attaining lower bounds on the achievable competitive ratio as a foundational objective for future research.