Ph.D Thesis

Ph.D StudentAvigdor-Elgrabli Noa
SubjectNew Algorithms for the Reordering Buffer Management
DepartmentDepartment of Computer Science
Supervisors ASSOCIATE PROF. Yuval Rabani
Full Thesis textFull thesis text - English Version


   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(loglog k). This matches the lower bound of Ω(loglog 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.

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(√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.

The third algorithm discussed here is a deterministic O((log k)/(loglog k))-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.