On the Advice Complexity of Online Problems

DOI10.1007/978-3-642-10631-6_35zbMath1272.68466OpenAlexW1947002865MaRDI QIDQ3652221

Richard Královič, Dennis Komm, Tobias Mömke, Rastislav Královič, Hans-Joachim Böckenhauer

Publication date: 17 December 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-10631-6_35

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (52)

Further Results on Online Node- and Edge-Deletion Problems with Advice ⋮ On the Power of Randomness versus Advice in Online Computation ⋮ Call admission problems on grids with advice ⋮ Online Bin Packing with Advice of Small Size ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Online Multi-Coloring with Advice ⋮ Job shop scheduling with unit length tasks ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Treasure Hunt with Advice ⋮ Disjoint Path Allocation with Sublinear Advice ⋮ On Energy-Efficient Computations With Advice ⋮ On the advice complexity of the \(k\)-server problem ⋮ Improved analysis of the online set cover problem with advice ⋮ Online Matching in Regular Bipartite Graphs ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ Advice complexity of disjoint path allocation ⋮ The advice complexity of a class of hard online problems ⋮ Fully Online Matching with Advice on General Bipartite Graphs and Paths ⋮ Online two-dimensional vector packing with advice ⋮ Reordering buffer management with advice ⋮ The online knapsack problem: advice and randomization ⋮ A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version ⋮ Modeling time criticality of information ⋮ Online two-way trading: randomization and advice ⋮ Advice Complexity and Barely Random Algorithms ⋮ Online coloring of bipartite graphs with and without advice ⋮ Online node- and edge-deletion problems with advice ⋮ Online algorithms with advice for bin packing and scheduling problems ⋮ The \(k\)-server problem with advice in \(d\) dimensions and on the sphere ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ On the Advice Complexity of the k-Server Problem ⋮ On the list update problem with advice ⋮ On the advice complexity of the online dominating set problem ⋮ Online algorithms with advice: the tape model ⋮ Unnamed Item ⋮ Weighted online problems with advice ⋮ Online Minimum Spanning Tree with Advice ⋮ Advice Complexity and Barely Random Algorithms ⋮ 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 ⋮ Weighted Online Problems with Advice ⋮ Advice Complexity of the Online Search Problem ⋮ Online bin packing with advice of small size ⋮ Towards using the history in online computation with advice ⋮ On online algorithms with advice for the \(k\)-server problem ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs ⋮ Exploring sparse graphs 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 Online Problems