Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities

Abstract. We consider the weighted Reordering Buffer Management problem. In this problem a set of n elements arrive over time one at a time and the elements can be stored in a buffer of size k. When the buffer becomes full, an element must be output. Elements are colored and if two elements are output consecutively and they have different colors then a switching cost is incurred. If the new color output is c, the cost is wc. The objective is to reorder the elements to minimize the total switching cost in the output sequence. In this paper, we give an improved randomized O(log log log kγ)-approximation for this problem where γ is the ratio of the maxi-mum to minimum weight of a color, improving upon the previous best O(log log kγ)-approximation. Our improvement builds on strengthening the standard linear program for the problem with non-standard knap-sack covering inequalities. In particular, by leveraging the structure of these inequalities, our algorithm manages to render several random pro-cedures more powerful and combine them effectively, thereby giving an exponential improvement upon the previous work.