Information Complexity of Online Problems
From MaRDI portal
Publication:3586068
DOI10.1007/978-3-642-15155-2_3zbMath1287.68083OpenAlexW1554718677MaRDI QIDQ3586068
Juraj Hromkovič, Richard Královič, Rastislav Královič
Publication date: 3 September 2010
Published in: Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-15155-2_3
Related Items (46)
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 Multi-Coloring with Advice ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Treasure Hunt with Advice ⋮ Disjoint Path Allocation with Sublinear Advice ⋮ On the advice complexity of the \(k\)-server problem ⋮ Improved analysis of the online set cover problem with advice ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ Advice Complexity of Fine-Grained Job Shop Scheduling ⋮ Call admission problems on trees ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ The advice complexity of a class of hard online problems ⋮ On Usefulness of Information: Framework and NFA Case ⋮ Fully Online Matching with Advice on General Bipartite Graphs and Paths ⋮ Relative Worst-Order Analysis: A Survey ⋮ Length-Weighted Disjoint Path Allocation ⋮ Second Thoughts on the Second Law ⋮ Online minimum spanning trees with weight predictions ⋮ Advice complexity of adaptive priority algorithms ⋮ Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems ⋮ Online knapsack with removal and recourse ⋮ Reordering buffer management with advice ⋮ The online knapsack problem: advice and randomization ⋮ Advice Complexity and Barely Random Algorithms ⋮ Online coloring of bipartite graphs with and without advice ⋮ Online node- and edge-deletion problems with advice ⋮ 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 ⋮ Online Minimum Spanning Tree with Advice ⋮ 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 ⋮ Online bin covering with advice ⋮ Advice Complexity of the Online Search Problem ⋮ 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: Information Complexity of Online Problems
