On the advice complexity of the set cover problem

DOI10.1007/978-3-642-30642-6_23MaRDI QIDQ2907505zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Improved analysis of the online set cover problem with advice
• Advice complexity for a class of online problems
• The advice complexity of a class of hard online problems
• The online set cover problem
• Online bin covering with advice

Cited in

(18)

• The advice complexity of a class of hard online problems
• Online budgeted maximum coverage
• Online multi-coloring with advice
• Improved analysis of the online set cover problem with advice
• The online knapsack problem: advice and randomization
• Online bin packing with advice
• Greedy algorithms for on-line set-covering
• On advice complexity of the k-server problem under sparse metrics
• A technique to obtain hardness results for randomized online algorithms -- a survey
• Advice complexity for a class of online problems
• Online graph coloring against a randomized adversary
• Online Multi-Coloring with Advice
• The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
• On the advice complexity of the \(k\)-server problem under sparse metrics
• Towards using the history in online computation with advice
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• 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

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

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