Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/38076
Title: Reordering Buffer Management with Advice
Authors: Van Stee, Rob
Rosen, Adi
Adamaszek, Anna
Renault, Marc. P.
First Published: 17-Jun-2016
Publisher: Springer Verlag
Citation: Journal of Scheduling, 2016, doi:10.1007/s10951-016-0487-8
Abstract: In the reordering buffer management problem, a sequence of colored items arrives at a service station to be processed. Each color change between two consecutively processed items generates some cost. A reordering buffer of capacity k items can be used to preprocess the input sequence in order to decrease the number of color changes. The goal is to find a scheduling strategy that, using the reordering buffer, minimizes the number of color changes in the given sequence of items. We consider the problem in the setting of online computation with advice. In this model, the color of an item becomes known only at the time when the item enters the reordering buffer. Additionally, together with each item entering the buffer, we get a fixed number of advice bits, which can be seen as information about the future or as information about an optimal solution (or an approximation thereof) for the whole input sequence. We show that for any ε>0 there is a (1+ε)-competitive algorithm for the problem which uses only a constant (depending on ε) number of advice bits per input item. This also immediately implies a (1+ε)-approximation algorithm which has 2O(nlog1/ε) running time (this should be compared to the trivial optimal algorithm which has a running time of kO(n)). We complement the above result by presenting a lower bound of Ω(logk) bits of advice per request for any 1-competitive algorithm.
DOI Link: 10.1007/s10951-016-0487-8
ISSN: 1094-6136
eISSN: 1099-1425
Links: http://link.springer.com/article/10.1007%2Fs10951-016-0487-8
http://hdl.handle.net/2381/38076
Embargo on file until: 17-Jun-2017
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © Springer Verlag, 2016. This version of this article is distributed under the terms of the Creative Commons Attribution-Non Commercial-No Derivatives License (http://creativecommons.org/licenses/by-nc-nd/4.0/ ), which permits use and distribution in any medium, provided the original work is properly cited, the use is non-commercial and no modifications or adaptations are made.
Description: Following the embargo period the above license applies.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
bufferReorderFinal.pdfPost-review (final submitted author manuscript)392.51 kBUnknownView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.