On the Advice Complexity of the Knapsack Problem

DOI10.1007/978-3-642-29344-3_6zbMath1297.68266OpenAlexW1542204506MaRDI QIDQ2894454

Richard Královič, Dennis Komm, Hans-Joachim Böckenhauer, Peter Rossmanith

Publication date: 29 June 2012

Published in: LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/68934

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (15)

Online Multi-Coloring with Advice ⋮ Treasure Hunt with Advice ⋮ On Energy-Efficient Computations With Advice ⋮ Improved analysis of the online set cover problem with advice ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ Fully Online Matching with Advice on General Bipartite Graphs and Paths ⋮ The online knapsack problem: advice and randomization ⋮ Online coloring of bipartite graphs with and without advice ⋮ Online node- and edge-deletion problems with advice ⋮ On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles ⋮ The string guessing problem as a method to prove lower bounds on the advice complexity ⋮ Towards using the history in online computation with advice ⋮ On Advice Complexity of the k-server Problem under Sparse Metrics ⋮ Online knapsack revisited

Uses Software

• Knapsack

This page was built for publication: On the Advice Complexity of the Knapsack Problem