TY - GEN

T1 - Online scheduling for sorting buffers

AU - Räcke, Harald

AU - Sohler, Christian

AU - Westermann, Matthias

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - We introduce the online scheduling problem for sorting buffers. A service station and a sorting buffer are given. An input sequence of items which are only characterized by a specific attribute has to be processed by the service station which benefits from consecutive items with the same attribute value. The sorting buffer which is a random access buffer with storage capacity for k items can be used to rearrange the input sequence. The goal is to minimize the cost of the service station, i.e., the number of maximal subsequences in its sequence of items containing only items with the same attribute value. This problem is motivated by many applications in computer science and economics. The strategies are evaluated in a competitive analysis in which the cost of the online strategy is compared with the cost of an optimal offline strategy. Our main result is a deterministic strategy that achieves a competitive ratio of 0(log2 k). In addition, we show that several standard strategies are unsuitable for this problem, i.e., we prove a lower bound of Ω(√k) on the competitive ratio of the First In First Out (FIFO) and Least Recently Used (LRU) strategy and of Ω(k) on the competitive ratio of the Largest Color First (LCF) strategy.

AB - We introduce the online scheduling problem for sorting buffers. A service station and a sorting buffer are given. An input sequence of items which are only characterized by a specific attribute has to be processed by the service station which benefits from consecutive items with the same attribute value. The sorting buffer which is a random access buffer with storage capacity for k items can be used to rearrange the input sequence. The goal is to minimize the cost of the service station, i.e., the number of maximal subsequences in its sequence of items containing only items with the same attribute value. This problem is motivated by many applications in computer science and economics. The strategies are evaluated in a competitive analysis in which the cost of the online strategy is compared with the cost of an optimal offline strategy. Our main result is a deterministic strategy that achieves a competitive ratio of 0(log2 k). In addition, we show that several standard strategies are unsuitable for this problem, i.e., we prove a lower bound of Ω(√k) on the competitive ratio of the First In First Out (FIFO) and Least Recently Used (LRU) strategy and of Ω(k) on the competitive ratio of the Largest Color First (LCF) strategy.

UR - http://www.scopus.com/inward/record.url?scp=38049128835&partnerID=8YFLogxK

U2 - 10.1007/3-540-45749-6_71

DO - 10.1007/3-540-45749-6_71

M3 - Conference contribution

AN - SCOPUS:38049128835

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 820

EP - 832

BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings

A2 - Möhring, Rolf

A2 - Raman, Rajeev

PB - Springer Verlag

T2 - 10th Annual European Symposium on Algorithms, ESA 2002

Y2 - 17 September 2002 through 21 September 2002

ER -