Access Restriction

Author Englert, Matthias ♦ Rglin, Heiko ♦ Westermann, Matthias
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Competitive ratio ♦ Online algorithms ♦ Reordering buffers
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 $\textit{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 $\textit{O}(log$ $\textit{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 $\textit{o}(&sqrt;log$ $\textit{k})$ upper bound on the competitive ratio of MAP. However, we also give some evidence that in fact MAP achieves a competitive ratio of $\textit{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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2010-01-05
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 14
Page Count 12
Starting Page 3.3
Ending Page 3.14

Open content in new tab

   Open content in new tab
Source: ACM Digital Library