Exploiting locality: Approximating sorting buffers

DOI10.1016/J.JDA.2006.08.001zbMATH Open1165.90599OpenAlexW2027240710MaRDI QIDQ925070FDOQ925070

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

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

zbMATH Keywords

approximation algorithmslocal-ratiosorting buffers

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A unified approach to approximating resource allocation and scheduling
• One for the price of two: a unified approach for approximating covering problems
• Automata, Languages and Programming
• LATIN 2004: Theoretical Informatics
• Title not available (Why is that?)

Cited In (10)

• Title not available (Why is that?)
• 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)