Name
Abstract | ||
|---|---|---|
We consider the reordering buffer problem on a line consisting of n equidistant points. We show that, for any constant δ, an (offline) algorithm that has a buffer (1−δ)⋅k performs worse by a factor of Ω(logn) than an offline algorithm with buffer k. In particular, this demonstrates that the O(logn)-competitive online algorithm MovingPartition by Gamzu and Segev (2009) [9] is essentially optimal against any offline algorithm with a slightly larger buffer. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.tcs.2017.10.008 | Theoretical Computer Science |
Keywords | DocType | Volume |
Reordering buffer,Competitive analysis | Journal | 707 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
7 | 8 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcin Bienkowski | 1 | 254 | 27.18 |
| Martin Böhm | 2 | 29 | 6.65 |
| Lukasz Jez | 3 | 61 | 11.93 |
| Paweł Laskoś-Grabowski | 4 | 0 | 0.34 |
| Jan Marcinkowski | 5 | 47 | 3.92 |
| jir sgall | 6 | 199 | 22.48 |
| Aleksandra Spyra | 7 | 0 | 0.34 |
| Pavel Veselý | 8 | 30 | 9.05 |