Offline list update is NP-hard

DOI10.1007/3-540-45253-2_5MaRDI QIDQ2753921zbMATH OpenFDO

Authors Christoph Ambühl

Publication date 18 December 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-45253-2_5

zbMATH Keywords

competitive analysislist-updateNPon-line algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Off-line algorithms for the list update problem
• Online and Offline Access to Short Lists
• Optimal strategies for the list update problem under the MRM alternative cost model
• Paid exchanges are worth the price
• A Survey of Algorithms and Models for List Update

Cited in

(10)

• Off-line algorithms for the list update problem
• Paid exchanges are worth the price
• On list update with locality of reference
• A Survey of Algorithms and Models for List Update
• Online and Offline Access to Short Lists
• Optimal strategies for the list update problem under the MRM alternative cost model
• Self-adjusting grid networks
• Self-adjusting linear networks
• List update with delays or time windows
• On the approximability of multistage min-sum set cover

This page was built for publication: Offline list update is NP-hard

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