Reordering buffer management with advice

Anna Adamaszek (), Marc P. Renault (), Adi Rosén () and Rob Stee ()
Additional contact information
Anna Adamaszek: University of Copenhagen
Marc P. Renault: CNRS and Université Paris Diderot
Adi Rosén: CNRS and Université Paris Diderot
Rob Stee: University of Leicester

Journal of Scheduling, 2017, vol. 20, issue 5, No 1, 423-442

Abstract: 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 $$\varepsilon > 0$$ ε > 0 there is a $$(1+\varepsilon )$$ ( 1 + ε ) -competitive algorithm for the problem which uses only a constant (depending on $$\varepsilon $$ ε ) number of advice bits per input item. This also immediately implies a $$(1+\varepsilon )$$ ( 1 + ε ) -approximation algorithm which has $$2^{O(n\log 1/\varepsilon )}$$ 2 O ( n log 1 / ε ) running time (this should be compared to the trivial optimal algorithm which has a running time of $$k^{O(n)}$$ k O ( n ) ). We complement the above result by presenting a lower bound of $$\varOmega (\log k)$$ Ω ( log k ) bits of advice per request for any 1-competitive algorithm.

Keywords: Reordering buffer management; Online algorithms; Online algorithms with advice; Competitive analysis (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-016-0487-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:20:y:2017:i:5:d:10.1007_s10951-016-0487-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-016-0487-8

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().