Online and offline algorithms for the sorting buffers problem on the line metric

DOI10.1016/J.JDA.2008.08.002MaRDI QIDQ2266935zbMATH OpenOpenAlexFDO

Authors Rohit Khandekar, Vinayaka Pandit

Publication date 26 February 2010

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

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

zbMATH Keywords

online algorithmsapproximation algorithmsmetric embedding

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Searching and sorting (68P10) Approximation algorithms (68W25)

Recommendations

• Offline Sorting Buffers on Line
• Online Sorting Buffers on Line
• Improved Online Algorithms for the Sorting Buffer Problem
• Improved online algorithms for the sorting buffer problem on line metrics
• scientific article; zbMATH DE number 5899288

Cites work

• scientific article; zbMATH DE number 5485491 (Why is no real title available?)
• scientific article; zbMATH DE number 1947443 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• A tight bound on approximating arbitrary metrics by tree metrics
• Algorithms for capacitated vehicle routing
• Automata, Languages and Programming
• Dial a Ride from k-Forest
• Exploiting locality: Approximating sorting buffers
• Improved Online Algorithms for the Sorting Buffer Problem
• LATIN 2004: Theoretical Informatics

Cited in

(10)

• Almost Tight Bounds for Reordering Buffer Management
• Online Sorting Buffers on Line
• Offline Sorting Buffers on Line
• A note on sorting buffers offline
• NP-hardness of the sorting buffer problem on the uniform metric
• LATIN 2004: Theoretical Informatics
• On-line sorting of twisted sequences in linear time
• Improved Online Algorithms for the Sorting Buffer Problem
• Logarithmic price of buffer downscaling on line metrics
• Improved online algorithms for the sorting buffer problem on line metrics

This page was built for publication: Online and offline algorithms for the sorting buffers problem on the line metric

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