Advice complexity for a class of online problems

DOI10.4230/LIPICS.STACS.2015.116MaRDI QIDQ2954988zbMATH OpenFDO

Authors Christian Kudahl, Jesper W. Mikkelsen, Joan Boyar, Lene M. Favrholdt

Publication date 24 January 2017

Full work available at URL https://arxiv.org/abs/1408.7033

zbMATH Keywords

online algorithmsadvice complexitycovering designsasymmetric string guessingadvice complexity class AOC

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The advice complexity of a class of hard online problems
• On the Advice Complexity of Online Problems
• On the advice complexity of the set cover problem
• Improved analysis of the online set cover problem with advice
• How Much Information about the Future Is Needed?

Cited in

(37)

• Dynamic node packing
• Online computation with untrusted advice
• On the advice complexity of the online dominating set problem
• The advice complexity of a class of hard online problems
• Online-bounded analysis
• On the power of advice and randomization for the disjoint path allocation problem
• Disjoint path allocation with sublinear advice
• Weighted online problems with advice
• Call admission problems on grids with advice
• Call admission problems on grids with advice (extended abstract)
• Independent set with advice: the impact of graph knowledge (extended abstract)
• On the advice complexity of buffer management
• On the advice complexity of the set cover problem
• Advice classes of parametrized tractability
• Online Minimum Spanning Tree with Advice
• Weighted Online Problems with Advice
• The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
• Towards using the history in online computation with advice
• A simple PTAS for the dual bin packing problem and advice complexity of its online version
• Advice complexity of disjoint path allocation
• Improved analysis of the online set cover problem with advice
• Advice complexity of the online induced subgraph problem
• Online bounded analysis
• On energy-efficient computations with advice
• Call admission problems on trees
• How Much Information about the Future Is Needed?
• Advice complexity: quantitative approach to a-priori information. Extended abstract
• Advice complexity of online non-crossing matching
• On the Advice Complexity of Online Edge- and Node-Deletion Problems
• On the Advice Complexity of Online Problems
• Tight bounds for the advice complexity of the online minimum Steiner tree problem
• Optimal online edge coloring of planar graphs with advice
• Online node- and edge-deletion problems with advice
• Further results on online node- and edge-deletion problems with advice
• Advice complexity of the online search problem
• Treasure hunt with advice
• Online algorithms with advice: the tape model

This page was built for publication: Advice complexity for a class of online problems

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