Online computation with advice

DOI10.1016/j.tcs.2010.08.007zbMath1218.68200OpenAlexW2109659895MaRDI QIDQ541670

Adi Rosén, Pierre Fraigniaud, Amos Korman, Yuval Emek

Publication date: 7 June 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.007

zbMATH Keywords

competitive analysisonline algorithmsadvice\(k\)-server problemmetrical task systems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

Related Items (60)

Online makespan minimization with parallel schedules ⋮ 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 ⋮ A fast approximate implementation of the work function algorithm for solving the \(k\)-server problem ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Online Multi-Coloring with Advice ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Online algorithms with advice for the dual bin packing problem ⋮ 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 ⋮ The ANTS problem ⋮ Improved analysis of the online set cover problem with advice ⋮ Finding the size and the diameter of a radio network using short labels ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ Advice Complexity of Fine-Grained Job Shop Scheduling ⋮ Deterministic size discovery and topology recognition in radio networks with short labels ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Advice complexity of disjoint path allocation ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ Fast rendezvous with advice ⋮ The advice complexity of a class of hard online problems ⋮ Length-Weighted Disjoint Path Allocation ⋮ Online minimum spanning trees with weight predictions ⋮ Advice complexity of adaptive priority algorithms ⋮ Online knapsack with removal and recourse ⋮ 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 ⋮ Online two-way trading: randomization and advice ⋮ Advice Complexity and Barely Random Algorithms ⋮ Online node- and edge-deletion problems with advice ⋮ Online algorithms with advice for bin packing and scheduling problems ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ 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 list update problem with advice ⋮ Impact of knowledge on election time in anonymous networks ⋮ On the advice complexity of the online dominating set problem ⋮ Online algorithms with advice: the tape model ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ Weighted online problems with advice ⋮ Online Minimum Spanning Tree with Advice ⋮ The string guessing problem as a method to prove lower bounds on the advice complexity ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ 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 ⋮ Distributed graph searching with a sense of direction ⋮ Topology recognition with advice ⋮ Online multi-coloring with advice ⋮ Online bin packing with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trade-offs between the size of advice and broadcasting time in trees
• Local MST computation with short advice
• Randomized algorithms for metrical task systems
• A competitive analysis of the list update problem with lookahead
• On competitive on-line paging with lookahead
• Ramsey-type theorems for metric spaces with applications to online problems
• On metric Ramsey-type phenomena
• Informative labeling schemes for graphs
• Competitive algorithms for server problems
• On the Additive Constant of the k-Server Work Function Algorithm
• An optimal on-line algorithm for metrical task system
• On the k -server conjecture
• Better Algorithms for Unfair Metrical Task Systems and Applications
• Approximate distance oracles
• Proof labeling schemes
• Distributed verification of minimum spanning trees
• Oracle size
• Graph Searching with Advice
• Distributed Computing with Advice: Information Sensitivity of Graph Coloring
• How Much Information about the Future Is Needed?
• Automata, Languages and Programming
• Tree Exploration with an Oracle
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Online computation with advice