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

advice complexityadvice complexity class AOCasymmetric string guessingcovering designsonline algorithms

Mathematics Subject Classification ID

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

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

(38)

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

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)