Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Reordering buffers for general metric spaces

Tools
- Tools
+ 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. doi:10.4086/toc.2010.v006a002 ISSN 1557-2862.

[img]
Preview
PDF
WRAP_Englert_Reordering_buffers.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution.

Download (338Kb)
Official URL: http://dx.doi.org/10.4086/toc.2010.v006a002

Request Changes to record.

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, Engineering and Medicine > 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
Dates:
DateEvent
2010Published
Volume: Vol.6
Number: No.1
Page Range: pp. 27-46
DOI: 10.4086/toc.2010.v006a002
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 1 August 2016
Date of first compliant Open Access: 1 August 2016
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)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us