Online and offline algorithms for the sorting buffers problem on the line metric
Online and offline algorithms for the sorting buffers problem on the line metric
复制标题
在线度量上排序缓冲区问题的在线和离线算法
DOI：
10.1016/j.jda.2008.08.002
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Vinayaka Pandit
中科院分区：
文献类型：
--
作者：
R. Khandekar;Vinayaka Pandit
我们考虑排序缓冲区问题。这个问题的输入是一个请求序列，每个请求由度量空间中的一个点指定。有一个“服务器”从一个点移动到另一个点来服务这些请求。为了满足一个请求，服务器需要访问与该请求对应的点。目标是最小化服务器在度量空间中行进的总距离。为了实现这一点，允许服务器以任何顺序服务请求，这需要在任何时候“缓冲”最多k个请求。因此，一个有效的重新排序可以只在服务了除k个之前的请求之外的所有请求之后才服务于一个请求。在本文中，我们考虑这个问题的线度量，这是出于其应用的磁盘调度问题。我们提出了非平凡的近似比在在线和离线设置的第一近似算法。在具有n个均匀间隔点的线度量上，我们给出了一个随机在线算法，其竞争比为O（log2n）。在离线设置中，我们的算法产生的第一个常数因子近似和运行在准多项式时间N n kO（logn），其中N是请求的总数。我们的方法是基于一个动态的程序，保持跟踪的数量在每个O（logn）线段的长度呈几何增长的未决请求。
We consider the sorting buffers problem. Input to this problem is a sequence of requests, each specified by a point in a metric space. There is a “server” that moves from point to point to serve these requests. To serve a request, the server needs to visit the point corresponding to that request. The objective is to minimize the total distance traveled by the server in the metric space. In order to achieve this, the server is allowed to serve the requests in any order that requires to “buffer” at most k requests at any time. Thus a valid reordering can serve a request only after serving all but k previous requests. In this paper, we consider this problem on the line metric which is motivated by its application to the disc scheduling problem. We present first approximation algorithms with non-trivial approximation ratios in both online and offline settings. On a line metric with n uniformly spaced points, we give a randomized online algorithm with a competitive ratio of O(log2n) in expectation against an oblivious adversary. In the offline setting, our algorithm yields the first constant-factor approximation and runs in quasi-polynomial time N⋅n⋅kO(logn)where N is the total number of requests. Our approach is based on a dynamic program that keeps track of the number of pending requests in each of O(logn) line segments that are geometrically increasing in length.