The Library

Reordering buffers for general metric spaces

Tools

Englert, Matthias, Raecke, Harald and Westermann, Matthias. (2010) Reordering buffers for general metric spaces. Theory of Computing, Vol.6 (No.1). pp. 27-46. ISSN 1557-2862

[img]
Preview
 PDF
WRAP_Englert_Reordering_buffers.pdf - Published Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Available under License Creative Commons Attribution.
Download (338Kb)

Abstract

In the reordering buffer problem, we are given an input sequence of requests for service each of which corresponds to a point in a metric space. The cost of serving the requests heavily depends on the processing order. When serving a request the cost is equal to the distance, in the metric space, between this request and the previously served request. A reordering buffer with storage capacity k can be used to reorder the input sequence in a restricted fashion so as to construct an output sequence with lower service cost. This simple and universal framework is useful for many applications in computer science and economics, e. g., disk scheduling, rendering in computer graphics, or painting shops in car plants.

In this paper, we design online algorithms for the reordering buffer problem where the goal is to minimize the total cost. Our main result is a strategy with a polylogarithmic competitive ratio for general metric spaces. Previous work on the reordering buffer problem only considered very restricted metric spaces. We obtain our result by first developing a deterministic algorithm for weighted trees whose competitive ratio depends on k and the hop-diameter of the tree. Then we show how to improve this competitive ratio to O(log2 k) for metric spaces that correspond to hierarchically well-separated trees. Combining this result with the results on the probabilistic approximation of arbitrary metrics by tree metrics due to Fakcharoenphol, Rao, and Talwar, we obtain a randomized strategy for general metric spaces that achieves a competitive ratio of O(log2 k · log n) in expectation against an oblivious adversary. Here n denotes the number of distinct points in the metric space. Note that the length of the input sequence can be much larger than n.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Buffer storage (Computer science) -- Mathematical models, Metric spaces
Journal or Publication Title: Theory of Computing
Publisher: University of Chicago, Department of Computer Science
ISSN: 1557-2862
Official Date: 2010
Volume: Vol.6
Number: No.1
Page Range: pp. 27-46
Identification Number: 10.4086/toc.2010.v006a002
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Funder: Deutsche Forschungsgemeinschaft (DFG), Engineering and Physical Sciences Research Council (EPSRC), University of Warwick. Centre for Discrete Mathematics and Its Applications, Sixth Framework Programme (European Commission) (FP6)
Grant number: WE 2842/1 (DFG), EP/F043333/1 (EPSRC), 001907 (FP6)
References:

[1] AMJAD ABOUD: Correlation clustering with penalties and approximating the recordering buffer
management problem. Master’s thesis, The Technion - Israel Institute of Technology, Janurary
2008. [Technion TR archive]. 29
[2] HOUMAN ALBORZI, ERIC TORNG, PATCHRAWAT UTHAISOMBUT, AND STEPHEN WAGNER:
The k-client problem. J. Algorithms, 41(2):115–173, 2001. [doi:10.1006/jagm.2001.1182]. 30
[3] NOA AVIGDOR-ELGRABLI AND YUVAL RABANI: An improved competitive algorithm for reordering
buffer management. In Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), pp.
13–21. ACM Press, 2010. 29
[4] REUVEN BAR-YEHUDA AND JONATHAN LASERSON: Exploiting locality: Approximating sorting
buffers. In Proc. 3rd Workshop on Approximation and Online Algorithms (WAOA), volume
3879 of Lecture Notes in Computer Science, pp. 69–81. Springer, 2005. [doi:10.1007/11671411 6].
28, 30
[5] YAIR BARTAL: Probabilistic approximations of metric spaces and its algorithmic applications. In
Proc. 37th FOCS, pp. 184–193. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548477].
29, 42
[6] YAIR BARTAL: On approximating arbitrary metrics by tree metrics. In Proc. 30th STOC, pp.
161–168. ACM Press, 1998. [doi:10.1145/276698.276725]. 29
[7] MATTHIAS ENGLERT, DENIZ ¨OZMEN, AND MATTHIAS WESTERMANN: The power of reordering
for online minimum makespan scheduling. In Proc. 49th FOCS, pp. 603–612. IEEE Comp.
Soc. Press, 2008. [doi:10.1109/FOCS.2008.46]. 30
[8] MATTHIAS ENGLERT, HEIKO R¨O GLIN, AND MATTHIAS WESTERMANN: Evaluation of online
strategies for reordering buffers. In Proc. 5th Internat. Workshop on Efficient and Experimental
Algorithms (WEA), volume 4007 of Lecture Notes in Computer Science, pp. 183–194. Springer,
2006. [doi:10.1007/11764298 17]. 29
[9] MATTHIAS ENGLERT AND MATTHIAS WESTERMANN: Reordering buffer management for nonuniform
cost models. In Proc. 32nd Internat. Colloquium on Automata, Languages and Programming
(ICALP), volume 3580 of Lecture Notes in Computer Science, pp. 627–638. Springer, 2005.
[doi:10.1007/11523468 51]. 28, 29, 31
[10] JITTAT FAKCHAROENPHOL, SATISH B. RAO, AND KUNAL TALWAR: A tight bound on approximating
arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004.
[doi:10.1016/j.jcss.2004.04.011]. 29, 31
[11] IFTAH GAMZU AND DANNY SEGEV: Improved online algorithms for the sorting buffer problem.
In Proc. 24th Symp. on Theoretical Aspects of Computer Science (STACS), volume 4393 of Lecture
Notes in Computer Science, pp. 658–669. Springer, 2007. [doi:10.1007/978-3-540-70918-3 56].
29, 30
[12] KAI GUTENSCHWAGER, SVEN SPIEKERMANN, AND STEFAN VOSS: A sequential ordering
problem in automotive paint shops. Internat. J. Production Research, 42(9):1865–1878, 2004.
[doi:10.1080/00207540310001646821]. 29
[13] ROHIT KHANDEKAR AND VINAYAKA PANDIT: Online and offline algorithms for the sorting
buffers problem on the line metric. J. Discrete Algorithms, 2008. [doi:10.1016/j.jda.2008.08.002].
28, 29, 30
[14] JENS S. KOHRT AND KIRK PRUHS: A constant factor approximation algorithm for sorting buffers.
In Proc. 6th Latin American Symp. on Theoretical Informatics (LATIN), volume 2976 of Lecture
Notes in Computer Science, pp. 193–202. Springer, 2004. [LATIN:fqbc84923gveuhlr]. 28, 30
[15] JENS KROKOWSKI, HARALD R¨ACKE, CHRISTIAN SOHLER, AND MATTHIAS WESTERMANN:
Reducing state changes with a pipeline buffer. In Proc. 9th Internat. Fall Workshop Vision, Modeling,
and Visualization (VMV), pp. 217–224. Aka GmbH, 2004. 29
[16] HARALD R¨ACKE, CHRISTIAN SOHLER, AND MATTHIAS WESTERMANN: Online scheduling
for sorting buffers. In Proc. 10th European Symp. on Algorithms (ESA), volume 2461 of Lecture
Notes in Computer Science, pp. 820–832. Springer, 2002. [doi:10.1007/3-540-45749-6 71,
ESA:mx7mdle1j62b5n3h]. 28, 29
[17] TOBY J. TEOREY AND TAD B. PINKERTON: A comparative analysis of disk scheduling policies.
Comm. ACM, 15(3):177–184, 1972. [doi:10.1145/361268.361278]. 28
URI: http://wrap.warwick.ac.uk/id/eprint/42236

Request changes to a record

Actions (login required)

View Item View Item

Document Downloads

More statistics for this item...