×

Offline sorting buffers on line. (English) Zbl 1135.90390

Asano, Tetsuo (ed.), Algorithms and computation. 17th international symposium, ISAAC 2006, Kolkata, India, December 18–20, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-49694-6/pbk). Lecture Notes in Computer Science 4288, 81-89 (2006).
Summary: We consider the offline 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 travelled 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 a line metric which is motivated by its application to a widely studied disc scheduling problem. On a line metric with \(N\) uniformly spaced points, our algorithm yields the first constant-factor approximation and runs in quasi-polynomial time \(O(m\cdot N\cdot k^{O(\log N)})\) where \(m\) 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(\log N)\) line segments that are geometrically increasing in length.
For the entire collection see [Zbl 1133.68002].

MSC:

90C27 Combinatorial optimization
90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
90C59 Approximation methods and heuristics in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI