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

Evaluation of online strategies for reordering buffers

Tools
- Tools
+ Tools

Englert, Matthias, Röglin, H. and Westermann, M. (2009) Evaluation of online strategies for reordering buffers. Experimental Algorithmics (JEA), Volume 14 . Article number 3. doi:10.1145/1498698.1564503 ISSN 1084-6654.

[img] PDF
a3_3-englert.pdf - Published Version
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (369Kb)
Official URL: http://dx.doi.org/10.1145/1498698.1564503

Request Changes to record.

Abstract

A sequence of objects that are characterized by their color has to be processed. Their processing order influences how efficiently they can be processed: Each color change between two consecutive objects produces costs. A reordering buffer, which is a random access buffer with storage capacity for k objects, can be used to rearrange this sequence online in such a way that the total costs are reduced. This concept is useful for many applications in computer science and economics.

The strategy with the best-known competitive ratio is MAP. An upper bound of O(log k) on the competitive ratio of MAP is known and a nonconstant lower bound on the competitive ratio is not known. Based on theoretical considerations and experimental evaluations, we give strong evidence that the previously used proof techniques are not suitable to show an o(&sqrt;log k) upper bound on the competitive ratio of MAP. However, we also give some evidence that in fact MAP achieves a competitive ratio of O(1).

Further, we evaluate the performance of several strategies on random input sequences experimentally. MAP and its variants RC and RR clearly outperform the other strategies FIFO, LRU, and MCF. In particular, MAP, RC, and RR are the only known strategies whose competitive ratios do not depend on the buffer size. Furthermore, MAP achieves the smallest competitive ratio.

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
Journal or Publication Title: Experimental Algorithmics (JEA)
Publisher: Association for Computing Machinery
ISSN: 1084-6654
Official Date: 1 December 2009
Dates:
DateEvent
1 December 2009Published
Volume: Volume 14
Article Number: Article number 3
DOI: 10.1145/1498698.1564503
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 28 July 2016

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

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