A Constant Factor Approximation Algorithm for Reordering Buffer Management

DOI10.1137/1.9781611973105.70MaRDI QIDQ5741778zbMATH OpenOpenAlexFDO

Authors Noa Avigdor-Elgrabli, Yuval Rabani

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.4504

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Abstract: In the reordering buffer management problem (RBM) a sequence of $n$ colored items enters a buffer with limited capacity $k$. When the buffer is full, one item is removed to the output sequence, making room for the next input item. This step is repeated until the input sequence is exhausted and the buffer is empty. The objective is to find a sequence of removals that minimizes the total number of color changes in the output sequence. The problem formalizes numerous applications in computer and production systems, and is known to be NP-hard. We give the first constant factor approximation guarantee for RBM. Our algorithm is based on an intricate "rounding" of the solution to an LP relaxation for RBM, so it also establishes a constant upper bound on the integrality gap of this relaxation. Our results improve upon the best previous bound of $O(sqrtlogk)$ of Adamaszek et al. (STOC 2011) that used different methods and gave an online algorithm. Our constant factor approximation beats the super-constant lower bounds on the competitive ratio given by Adamaszek et al. This is the first demonstration of an offline algorithm for RBM that is provably better than any online algorithm.

Recommendations

• New Approximations for Reordering Buffer Management
• An improved competitive algorithm for reordering buffer management
• An improved competitive algorithm for reordering buffer management
• Almost Tight Bounds for Reordering Buffer Management
• Almost tight bounds for reordering buffer management
• A bicriteria approximation for the reordering buffer problem
• LATIN 2004: Theoretical Informatics
• scientific article; zbMATH DE number 7204485
• On the randomized competitive ratio of reordering buffer management with non-uniform costs
• Evaluation of Online Strategies for Reordering Buffers

Cited in

(16)

• A cost-based buffer replacement algorithm for object-oriented database systems
• Reordering buffer management with advice
• Tight bounds for online coloring of basic graph classes
• The time buffer approximated buffer allocation problem: a row-column generation approach
• Stochastic dominance and the bijective ratio of online algorithms
• A bicriteria approximation for the reordering buffer problem
• Generalized Reordering Buffer Management
• Reordering buffer management with advice
• On the randomized competitive ratio of reordering buffer management with non-uniform costs
• Weighted reordering buffer improved via variants of knapsack covering inequalities
• scientific article; zbMATH DE number 220697 (Why is no real title available?)
• New Approximations for Reordering Buffer Management
• Buffered Resource Constraint: Algorithms and Complexity
• Almost tight bounds for reordering buffer management
• Almost Tight Bounds for Reordering Buffer Management
• LATIN 2004: Theoretical Informatics

This page was built for publication: A Constant Factor Approximation Algorithm for Reordering Buffer Management

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741778)