Exploiting locality: Approximating sorting buffers

DOI10.1016/j.jda.2006.08.001zbMath1165.90599OpenAlexW2027240710MaRDI QIDQ925070

Jonathan Laserson, Reuven Bar Yehuda

Publication date: 29 May 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.08.001

zbMATH Keywords

approximation algorithmslocal-ratiosorting buffers

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities ⋮ A note on sorting buffers offline ⋮ NP-hardness of the sorting buffer problem on the uniform metric ⋮ Buffer management for colored packets with deadlines ⋮ Online and offline algorithms for the sorting buffers problem on the line metric ⋮ Almost Tight Bounds for Reordering Buffer Management

Cites Work

• Unnamed Item
• Unnamed Item
• One for the price of two: a unified approach for approximating covering problems
• Automata, Languages and Programming
• A unified approach to approximating resource allocation and scheduling
• LATIN 2004: Theoretical Informatics