Reordering Buffer Management
Algorithms and Experiments
Medha Vasanth

In the Reordering Buffer Management (RBM) problem, we are given an input sequence of size \(N\) and a buffer of size \(k\). Every item in the input sequence is characterized by a specific attribute commonly referred to as its "colour". We incur a cost when we switch from one colour to another. Our goal is to reorder this input sequence using the buffer such that the cost of switching between colours is minimized, in other words we aim to have long subsequences of items of the same colour. In this seminar, we present different existing algorithms for this problem, introduce our new algorithm and present experimental results comparing the different algorithms.