On the advice complexity of the knapsack problem

DOI10.1007/978-3-642-29344-3_6MaRDI QIDQ2894454zbMATH OpenOpenAlexFDO

Authors Dennis Komm, Richard Královič, 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

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

Recommendations

• The online knapsack problem: advice and randomization
• On the power of randomness versus advice in online computation
• On the Advice Complexity of Online Problems
• Online bin packing with advice of small size
• Online bin packing with advice

Cited in

(16)

• Online node- and edge-deletion problems with advice
• Improved analysis of the online set cover problem with advice
• The online knapsack problem: advice and randomization
• Online knapsack revisited
• On advice complexity of the k-server problem under sparse metrics
• A technique to obtain hardness results for randomized online algorithms -- a survey
• On energy-efficient computations with advice
• Online Multi-Coloring with Advice
• Treasure hunt with advice
• On the advice complexity of online bipartite matching and online stable marriage
• Online coloring of bipartite graphs with and without advice
• Towards using the history in online computation with advice
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• Online unbounded knapsack
• 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

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: On the advice complexity of the knapsack problem

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