An Improved Competitive Algorithm for Reordering Buffer Management

We design and analyze an online reordering buffer management algorithm with improved O (log k /log log k ) competitive ratio for nonuniform costs, where k is the buffer size. This improves on the best previous result (even for uniform costs) of Englert and Westermann (2005) giving O (log k ) competitive ratio, which was also the best (offline) 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 that we introduce in this article.