Technical Report PHD-2014-06

TR#:PHD-2014-06
Class:PHD
Title: New Algorithms for the Reordering Buffer Management Problem
Authors: Noa Avigdor-Elgrabli
Supervisors: Yuval Rabani
PDFPHD-2014-06.pdf
Abstract: This thesis focuses on the reordering buffer management problem (RBM). In RBM a sequence of $n$ colored items enters a buffer with limited capacity $k$. When the buffer is full, one item is removed to the output sequence, making room for the next input item. This step is repeated until the input sequence is exhausted and the buffer is empty. The objective is to find a sequence of removals that minimizes the total context switching cost in the output sequence. In the uniform cost model the context switching cost is simply the number of color changes. There are other cost models, for instance non-uniform costs where the cost of switching to a color depends on the color. An offline algorithm knows the entire input sequence in advance. An online algorithm must base its decisions only on the content of the buffer and the items it has seen so far (without knowing the future input sequence). This problem formalizes numerous applications in computer and production systems, and the offline version is known to be NP-hard.

In this thesis we present three reordering buffer management algorithms. All three are based on a linear programming relaxation for RBM that we introduce. Our main result is a randomized online algorithm for uniform cost functions. This result resolves the randomized competitive ratio of RBM. We prove that its competitive ratio is $O(\log\log k)$. This matches the lower bound of $\Omega(\log\log k)$ of Adamaszek et al. This is also the first randomized online algorithms for RBM. Our work demonstrates an exponential gap between the deterministic and the randomized competitive ratio of RBM. Our algorithm applies the general two-stage approach of the online primal-dual schema. The first stage is a deterministic online algorithm that computes a feasible fractional solution to our LP relaxation for reordering buffer management. As we compute the LP solution, we feed it to the second stage---a randomized online algorithm that converts the fractional solution into an integral solution.

The second algorithm is a deterministic offline algorithm for uniform cost functions. We present the first constant factor approximation guarantee for RBM. Our algorithm is based on a complicated ``rounding" of the solution to our LP relaxation for RBM, so it also establishes a constant upper bound on the integrality gap of this relaxation. Our results improve upon the best previous bound of $O(\sqrt{\log k})$ of Adamaszek et al. (STOC 2011). This is the first demonstration of a polynomial time offline algorithm for RBM that is provably better than any online algorithm. (Adamaszek et al. proved super-constant online lower bounds for RBM.) Some of the ideas used in this algorithm are used in the second stage of the above-mentioned randomized online algorithm. In the online case we employ randomness to replace the prescience needed in the offline case.

The third algorithm discussed here is a deterministic $O\left(\frac{\log k}{\log\log k}\right)$-competitive online algorithm for non-uniform cost functions. It improves the $O(\log k)$-competitive algorithm that was known before. This is the best deterministic online algorithm known for unrestricted non-uniform costs. Its analysis is an intricate dual fitting argument that uses the same LP relaxation discussed above. Our online algorithm does not solve the relaxation. In the analysis, we use the algorithm to generate a dual solution and we bound the gap between the cost of the algorithm and the cost of the dual solution. This approach is also one of the ingredients in our design and analysis of the optimal randomized online algorithm.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2014/PHD/PHD-2014-06), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2014
To the main CS technical reports page

Computer science department, Technion
admin