On the Advice Complexity of the Set Cover Problem

DOI10.1007/978-3-642-30642-6_23zbMath1360.68910OpenAlexW1544299159MaRDI QIDQ2907505

Tobias Mömke, Dennis Komm, Richard Královič

Publication date: 10 September 2012

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Related Items (15)

Online Multi-Coloring with Advice ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Improved analysis of the online set cover problem with advice ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ The advice complexity of a class of hard online problems ⋮ Fully Online Matching with Advice on General Bipartite Graphs and Paths ⋮ The online knapsack problem: advice and randomization ⋮ Online budgeted maximum coverage ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ 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 multi-coloring with advice ⋮ Online bin packing with advice

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