Experimental Evaluation of Reordering Buffer Management Algorithms

In the Reordering Buffer Management (RBM) problem, we are given an input sequence of size N and a buffer B of size k (k < N). Each item in the input sequence is characterized by its "colour''. The defining characteristic of this problem is that a cost is incurred when we switch from one colour to another in the resulting output sequence. Our goal is to permute the input sequence using the buffer B such that the cost of switching between colours is minimized. In the online version, the input sequence is not known in advance. We propose a new algorithm in this thesis, Accelerated Threshold (Acc-T) for the online version of the RBM problem with non-uniform costs. This thesis also presents experimental results for several existing uniform and non-uniform cost algorithms and compares them against different combinations of input sequence types, cost functions, buffer sizes and number of colours.