New Approximations for Reordering Buffer Management

In this paper we consider the buffer reordering management problem. In this model there are n elements that arrive over time with different colors. There is a buffer that can store up to k elements and when the buffer becomes full an element must be output. If an element is output that has a color different from the previous element, a cost depending on the color must be paid. This cost could be uniform or non-uniform over colors; these are called unweighted and weighted cases, respectively. The goal is to reorder elements within the buffer before outputting them to minimize the total cost incurred. There has been a search over the last decade to resolve the complexity of this problem online and offline. Very recently, there has been substantial progress for the unweighted case – an O (1)-approximation algorithm and an O (log log k )-competitive randomized algorithm were given [6, 7]. These results resolve the complexity of the unweighted buffer problem, up to constant factors, since the problem is NP-Hard and there is a matching lower bound on the competitive ratio. However, the progress for the weighted case has not been as satisfactory as for the unweighted case. Our main result is a randomized O (loglog kγ )-approximation for the weighted case, which gives an exponential improvement over the previously best known result of O ( y /l ogk ) which assumed γ = poly( k ). Here γ is the ratio of the maximum to minimum weight. We also revisit the unweighted case and give an improved randomized 66. 0823-approximation which improves (modestly) upon the approximation guarantee given in [6]. The algorithm and analysis we use for the unweighted case was done independently of [6]. We believe that our new interpretation of the problem and our analysis of an underlying random process could be of potential use in other settings.

Authors

• Sungjin Im
• Benjamin Moseley

Keywords

No keywords are indexed for this paper.