Experimental Evaluation of Reordering Buffer Management Algorithms

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Vasanth, Medha




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.


Computer Science




Carleton University

Thesis Degree Name: 

Master of Computer Science: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).