The Library
Reordering buffer management for non-uniform cost models
Tools
Englert, Matthias and Westermann, Matthias (2005) Reordering buffer management for non-uniform cost models. In: Caires, Luís and Italiano, Giuseppe F. and Monteiro, Luís and Palamidessi, Catuscia and Yung, Moti , (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, Volume 3580 . Springer Berlin Heidelberg, pp. 627-638. ISBN 9783540275800
PDF
fulltext24.pdf Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (166Kb) |
Official URL: http://dx.doi.org/10.1007/11523468_51
Abstract
A sequence of objects which 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 non-uniform cost. A reordering buffer which is a random access buffer with storage capacity for k objects can be used to rearrange this sequence in such a way that the total cost are minimized. This concept is useful for many applications in computer science and economics.
We show that a reordering buffer reduces the cost of each sequence by a factor of at most 2k–1. This result even holds for cost functions modeled by arbitrary metric spaces. In addition, a matching lower bound is presented. From this bound follows that each strategy that does not increase the cost of a sequence is at least (2k–1)-competitive.
As main result, we present the deterministic Maximum Adjusted Penalty (MediaObjects/InlineFigure1.png) strategy which is O(log k)-competitive. Previous strategies only achieve a competitive ratio of k in the non-uniform model. For the upper bound on MediaObjects/InlineFigure2.png, we introduce a basic proof technique. We believe that this technique can be interesting for other problems.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
ISBN: | 9783540275800 | ||||
Book Title: | Automata, Languages and Programming | ||||
Editor: | Caires, Luís and Italiano, Giuseppe F. and Monteiro, Luís and Palamidessi, Catuscia and Yung, Moti | ||||
Official Date: | 2005 | ||||
Dates: |
|
||||
Volume: | Volume 3580 | ||||
Page Range: | pp. 627-638 | ||||
DOI: | 10.1007/11523468_51 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |