On Advice Complexity of the k-server Problem under Sparse Metrics

DOI10.1007/978-3-319-03578-9_5zbMath1346.68263OpenAlexW1847140466MaRDI QIDQ2868631

Sushmita Gupta, Shahin Kamali, Alejandro López-Ortiz

Publication date: 17 December 2013

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03578-9_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Related Items (14)

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 ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ The advice complexity of a class of hard online problems ⋮ Online algorithms with advice for bin packing and scheduling problems ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ On the list update problem with advice ⋮ On the advice complexity of the online dominating set problem ⋮ Online algorithms with advice: the tape model ⋮ Advice Complexity of the Online Search Problem ⋮ Towards using the history in online computation with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Compact and low delay routing labeling scheme for unit disk graphs
• Online computation with advice
• A randomized algorithm for two servers in cross polytope spaces
• The 3-server problem in the plane.
• On the competitive ratio of the work function algorithm for the \(k\)-server problem
• Advice Complexity of Online Coloring for Paths
• On the Advice Complexity of the Knapsack Problem
• On Online Algorithms with Advice for the k-Server Problem
• On the Advice Complexity of the Set Cover Problem
• Online Graph Exploration with Advice
• Online Coloring of Bipartite Graphs with and without Advice
• On the Advice Complexity of the k-Server Problem
• Compact Navigation and Distance Oracles for Graphs with Small Treewidth
• Advice Complexity and Barely Random Algorithms
• An Optimal On-Line Algorithm for K Servers on Trees
• Information Complexity of Online Problems
• On the Advice Complexity of Online Problems
• Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
• The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Collective tree spanners of graphs

This page was built for publication: On Advice Complexity of the k-server Problem under Sparse Metrics