The \(k\)-server problem
From MaRDI portal
Publication:458484
DOI10.1016/j.cosrev.2009.04.002zbMath1302.68329OpenAlexW2100311357MaRDI QIDQ458484
Publication date: 7 October 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2009.04.002
Queues and service in operations research (90B22) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Online algorithms; streaming algorithms (68W27)
Related Items (27)
Randomized online computation with high probability guarantees ⋮ A fast work function algorithm for solving the \(k\)-server problem ⋮ A fast approximate implementation of the work function algorithm for solving the \(k\)-server problem ⋮ On the advice complexity of the \(k\)-server problem ⋮ Efficient algorithms for ride-hitching in UAV travelling ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ The median routing problem for simultaneous planning of emergency response and non-emergency jobs ⋮ An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ Online ride-hitching in UAV travelling ⋮ Optimal online algorithms for the multi-objective time series search problem ⋮ Reallocating multiple facilities on the line ⋮ The \(K\)-server problem via a modern optimization lens ⋮ Dynamic pricing of servers on trees ⋮ The \(k\)-server problem with advice in \(d\) dimensions and on the sphere ⋮ On the Advice Complexity of the k-Server Problem ⋮ The k-Server Problem with Delays on the Uniform Metric Space ⋮ The \(k\)-resource problem in uniform metric spaces ⋮ Metrical service systems with multiple servers ⋮ A new upper bound on the work function algorithm for the \(k\)-server problem ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Stochastic dominance and the bijective ratio of online algorithms ⋮ Multi-Finger Binary Search Trees ⋮ The traveling \(k\)-median problem: approximating optimal network coverage ⋮ The online \(k\)-server problem with rejection ⋮ The online \(k\)-server problem with max-distance objective ⋮ Memoryless algorithms for the generalized k-server problem on uniform metrics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Shortest paths without a map
- New algorithms for an ancient scheduling problem.
- Online algorithms. The state of the art
- Competitive snoopy caching
- A competitive 2-server algorithm
- HARMONIC is 3-competitive for two servers
- On the power of randomization in on-line algorithms
- Competitive randomized algorithms for nonuniform problems
- Competitive \(k\)-server algorithms
- The 2-evader problem
- Competitive analysis of randomized paging algorithms
- More on random walks, electrical networks, and the harmonic \(k\)-server algorithm.
- The 3-server problem in the plane.
- The weighted 2-server problem
- On the competitive ratio of the work function algorithm for the \(k\)-server problem
- On metric Ramsey-type phenomena
- On the k-server conjecture
- 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
- Self-adjusting binary search trees
- How to learn an unknown environment. I
- On fast algorithms for two servers
- Competitive paging algorithms
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- Competitive Algorithms for Layered Graph Traversal
- Fairness in Scheduling
- Generosity Helps or an 11-Competitive Algorithm for Three Servers
- An optimal on-line algorithm for metrical task system
- On the k -server conjecture
- Better Algorithms for Unfair Metrical Task Systems and Applications
- Beyond Competitive Analysis
- Exploring an unknown graph
- Linear programming without the matrix
- On the value of information in distributed decision-making (extended abstract)
- A Primal-Dual Randomized Algorithm for Weighted Paging
- The harmonic k -server algorithm is competitive
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: The \(k\)-server problem
