Reordering buffer management with advice

DOI10.1007/S10951-016-0487-8MaRDI QIDQ1707821zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anna Adamaszek, Marc P. Renault, Adi Rosén, Rob van Stee

Publication date 4 April 2018

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-016-0487-8

zbMATH Keywords

online algorithmscompetitive analysisonline algorithms with advicereordering buffer management

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Reordering buffer management with advice
• A Constant Factor Approximation Algorithm for Reordering Buffer Management
• Automata, Languages and Programming
• Generalized Reordering Buffer Management
• On the advice complexity of buffer management

Cites work

• scientific article; zbMATH DE number 5899288 (Why is no real title available?)
• scientific article; zbMATH DE number 1947443 (Why is no real title available?)
• A Constant Factor Approximation Algorithm for Reordering Buffer Management
• A note on sorting buffers offline
• A sequential ordering problem in automotive paint shops
• Advice complexity and barely random algorithms
• Almost tight bounds for reordering buffer management
• An improved competitive algorithm for reordering buffer management
• Automata, Languages and Programming
• How Much Information about the Future Is Needed?
• Information complexity of online problems
• NP-hardness of the sorting buffer problem on the uniform metric
• On online algorithms with advice for the k-server problem
• On the Advice Complexity of Online Problems
• On the advice complexity of buffer management
• On the advice complexity of the \(k\)-server problem
• Online algorithms with advice for bin packing and scheduling problems
• Online computation with advice
• Online makespan scheduling with sublinear advice
• The string guessing problem as a method to prove lower bounds on the advice complexity

Cited in

(3)

• Reordering buffer management with advice
• Almost Tight Bounds for Reordering Buffer Management
• Generalized Reordering Buffer Management

This page was built for publication: Reordering buffer management with advice

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