On the advice complexity of the \(k\)-server problem under sparse metrics
From MaRDI portal
Publication:503460
DOI10.1007/s00224-015-9649-xzbMath1401.68368arXiv1305.2108OpenAlexW2467644617MaRDI QIDQ503460
Alejandro López-Ortiz, Shahin Kamali, Sushmita Gupta
Publication date: 12 January 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1305.2108
Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)
Related Items
Call admission problems on grids with advice, Fully Online Matching with Advice on General Bipartite Graphs and Paths, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere, Online bin packing with advice of small size
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Compact and low delay routing labeling scheme for unit disk graphs
- Online coloring of bipartite graphs with and without advice
- On the list update problem with advice
- Online computation with advice
- A randomized algorithm for two servers in cross polytope spaces
- 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
- Graph minors. III. Planar tree-width
- S-functions for graphs
- Competitive randomized algorithms for nonuniform problems
- The 2-evader problem
- The 3-server problem in the plane.
- On the competitive ratio of the work function algorithm for the \(k\)-server problem
- On embedding trees into uniformly convex Banach spaces
- The online knapsack problem: advice and randomization
- On Advice Complexity of the k-server Problem under Sparse Metrics
- Advice Complexity of Online Coloring for Paths
- On Online Algorithms with Advice for the k-Server Problem
- On the Advice Complexity of the Set Cover Problem
- Online Graph Exploration with 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
- Random walks on weighted graphs and applications to on-line algorithms
- An Optimal On-Line Algorithm for K Servers on Trees
- New Ressults on Server Problems
- Competitive algorithms for server problems
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- On the k -server conjecture
- Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
- Advice Complexity of the Online Coloring Problem
- Collective Tree Spanners and Routing in AT-free Related Graphs
- How Much Information about the Future Is Needed?
- Collective tree spanners of graphs
