An improved competitive algorithm for reordering buffer management
Noa Avigdor-Elgrabli, Yuval Rabani · 2010
We design and analyze an on-line reordering buffer) management algorithm with improved O log k log log k competitive ratio for non-uniform costs, where k is the buffer size. 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 that we introduce in this paper.