TY - GEN
T1 - Online stochastic reordering buffer scheduling
AU - Esfandiari, Hossein
AU - Hajiaghayi, Mohammadtaghi
AU - Khani, Mohammad Reza
AU - Liaghat, Vahid
AU - Mahini, Hamid
AU - Räcke, Harald
PY - 2014
Y1 - 2014
N2 - In this paper we consider online buffer scheduling problems in which an online stream of n items (jobs) with different colors (types) has to be processed by a machine with a buffer of size k. In the standard model initially introduced by Räcke, Sohler, and Westermann [31], the machine chooses an active color and processes items whose color matches that color until no item in the buffer has the active color (note that the buffer is refilled in each step). In the block-operation model, the machine chooses an active color and can-in each step-process all items of that color in the buffer. Motivated by practical applications in real-world, we assume we have prior stochastic information about the input. In particular, we assume that the colors of items are drawn i.i.d. from a possibly unknown distribution, or more generally, the items are coming in a random order. In the random order setting, an adversary determines the color of each item in advance, but then the items arrive in a random order in the input stream. To the best of our knowledge, this is the first work which considers the reordering buffer problem in stochastic settings. Our main result is demonstrating constant competitive online algorithms for both the standard model and the block operation model in the unknown distribution setting and more generally in the random order setting. This provides a major improvement of the competitiveness of algorithms in stochastic settings; the best competitive ratio in the adversarial setting is Θ(loglogk) for both the standard and the block-operation models by Avigdor-Elgrabli and Rabani [8] and Adamaszek et al. [3]. Along the way, we also show that in the random order setting, designing competitive algorithms with the same competitive ratios (up to constant factors) in both the block operation model and the standard model are equivalent. To the best of our knowledge this is the first result of this type which relates an algorithm for the standard model to an algorithm for the block-operation model. Last but not least, we show in the uniform distribution setting, in which the probabilities of appearances of all colors are the same, a simple greedy algorithm is the best online algorithm in both models.
AB - In this paper we consider online buffer scheduling problems in which an online stream of n items (jobs) with different colors (types) has to be processed by a machine with a buffer of size k. In the standard model initially introduced by Räcke, Sohler, and Westermann [31], the machine chooses an active color and processes items whose color matches that color until no item in the buffer has the active color (note that the buffer is refilled in each step). In the block-operation model, the machine chooses an active color and can-in each step-process all items of that color in the buffer. Motivated by practical applications in real-world, we assume we have prior stochastic information about the input. In particular, we assume that the colors of items are drawn i.i.d. from a possibly unknown distribution, or more generally, the items are coming in a random order. In the random order setting, an adversary determines the color of each item in advance, but then the items arrive in a random order in the input stream. To the best of our knowledge, this is the first work which considers the reordering buffer problem in stochastic settings. Our main result is demonstrating constant competitive online algorithms for both the standard model and the block operation model in the unknown distribution setting and more generally in the random order setting. This provides a major improvement of the competitiveness of algorithms in stochastic settings; the best competitive ratio in the adversarial setting is Θ(loglogk) for both the standard and the block-operation models by Avigdor-Elgrabli and Rabani [8] and Adamaszek et al. [3]. Along the way, we also show that in the random order setting, designing competitive algorithms with the same competitive ratios (up to constant factors) in both the block operation model and the standard model are equivalent. To the best of our knowledge this is the first result of this type which relates an algorithm for the standard model to an algorithm for the block-operation model. Last but not least, we show in the uniform distribution setting, in which the probabilities of appearances of all colors are the same, a simple greedy algorithm is the best online algorithm in both models.
UR - http://www.scopus.com/inward/record.url?scp=84904187677&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-43948-7_39
DO - 10.1007/978-3-662-43948-7_39
M3 - Conference contribution
AN - SCOPUS:84904187677
SN - 9783662439470
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 465
EP - 476
BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PB - Springer Verlag
T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
Y2 - 8 July 2014 through 11 July 2014
ER -