Exploiting locality: Approximating sorting buffers

DOI10.1016/J.JDA.2006.08.001MaRDI QIDQ925070zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Approximation and Online Algorithms
• LATIN 2004: Theoretical Informatics
• A note on sorting buffers offline
• scientific article; zbMATH DE number 1947443
• Improved Online Algorithms for the Sorting Buffer Problem

Cites work

• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• scientific article; zbMATH DE number 1833399 (Why is no real title available?)
• A unified approach to approximating resource allocation and scheduling
• Automata, Languages and Programming
• LATIN 2004: Theoretical Informatics
• One for the price of two: a unified approach for approximating covering problems

Cited in

(10)

• scientific article; zbMATH DE number 1947443 (Why is no real title available?)
• Almost Tight Bounds for Reordering Buffer Management
• Hierarchical bin buffering
• Buffer management for colored packets with deadlines
• A note on sorting buffers offline
• NP-hardness of the sorting buffer problem on the uniform metric
• LATIN 2004: Theoretical Informatics
• Online and offline algorithms for the sorting buffers problem on the line metric
• Approximation and Online Algorithms
• Weighted reordering buffer improved via variants of knapsack covering inequalities

This page was built for publication: Exploiting locality: Approximating sorting buffers

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