Name
Title | ||
|---|---|---|
On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs |
Abstract | ||
|---|---|---|
Reordering buffer management (RBM) is an elegant theoretical model that captures the tradeoff between buffer size and switching costs for a variety of reordering/sequencing problems. In this problem, colored items arrive over time, and are placed in a buffer of size k. When the buffer becomes full, an item must be removed from the buffer. A penalty cost is incurred each time the sequence of removed items switches colors. In the non-uniform cost model, there is a weight w(c) associated with each color c, and the cost of switching to color c is w(c). The goal is to minimize the total cost of the output sequence, using the buffer to rearrange the input sequence. Recently, a randomized O(log log k)-competitive online algorithm was given for the case that all colors have the same weight (FOCS 2013). This is an exponential improvement over the nearly tight bound of O(root log k) on the deterministic competitive ratio of that version of the problem (Adamaszek et al., STOC 2011). In this paper, we give an O((log log k gamma)(2))-competitive algorithm for the non-uniform case, where. is the ratio of the maximum to minimum color weight. Our work demonstrates that randomness can achieve exponential improvement in the competitive ratio even for the non-uniform case. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-47672-7_7 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Online algorithm,Discrete mathematics,Combinatorics,Colored,Computer science,Total cost,Competitive analysis | Conference | 9134 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 0.46 |
References | Authors | |
12 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noa Avigdor-Elgrabli | 1 | 54 | 4.48 |
| Sungjin Im | 2 | 353 | 33.73 |
| Benjamin Moseley | 3 | 554 | 50.11 |
| Yuval Rabani | 4 | 2265 | 274.98 |