Title:  An Improved Competitive Algorithm for Reordering Buffer  
        Management

Speaker: Noa Elgrabli, Technion 

Abstract: 

In the reordering buffer management problem, a stream of colored
items arrives at a service station equipped with a buffer that
has a limited storage capacity of $k$ items. The buffer is used
to permute the input stream (in a limited way) in order to
minimize the context switching cost, which is incurred whenever
there is a color change between consecutive items served.
In our work we design and analyze an on-line reordering
buffer management algorithm with improved
$O\left(\frac{\log k}{\log\log k}\right)$ competitive ratio
for non-uniform costs. This improves on the best previous result
(even for uniform costs) of Englert and Westermann (ICALP 2005)
giving $O(\log k)$ competitive ratio, which was also the best
(off-line) polynomial time approximation guarantee for this problem.
Our analysis is based on an intricate dual fitting argument using
a linear programming relaxation for the problem.

joint work with Yuval Rabani