On the k -server conjecture
From MaRDI portal
Publication:4369887
DOI10.1145/210118.210128zbMath0885.68075DBLPjournals/jacm/KoutsoupiasP95OpenAlexW2069255833WikidataQ29010485 ScholiaQ29010485MaRDI QIDQ4369887
Elias Koutsoupias, Christos H. Papadimitriou
Publication date: 28 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/210118.210128
Related Items (66)
A simple analysis of the harmonic algorithm for two servers ⋮ The weighted 2-server problem ⋮ On the competitive ratio of the work function algorithm for the \(k\)-server problem ⋮ A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line ⋮ Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications ⋮ Serving Online Requests with Mobile Servers ⋮ On the remote server problem or more about TCP acknowledgments ⋮ On the advice complexity of the \(k\)-server problem ⋮ Randomized competitive analysis for two server problems ⋮ Efficient algorithms for ride-hitching in UAV travelling ⋮ The work function algorithm for the paging problem ⋮ Approximation algorithms for clustering with dynamic points ⋮ On the additive constant of the \(k\)-server work function algorithm ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ A \(o(n)\)-competitive deterministic algorithm for online matching on a line ⋮ The minimum backlog problem ⋮ Competitive Algorithms for Generalized k -Server in Uniform Metrics ⋮ More on randomized on-line algorithms for caching. ⋮ A randomized algorithm for two servers in cross polytope spaces ⋮ Competitive algorithms for the bicriteria \(k\)-server problem ⋮ Online ride-hitching in UAV travelling ⋮ The \(k\)-server problem ⋮ A \(k\)-server problem with parallel requests and unit distances ⋮ Reallocating multiple facilities on the line ⋮ Randomized Competitive Analysis for Two-Server Problems ⋮ The \(K\)-server problem via a modern optimization lens ⋮ A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching ⋮ ON THE k-TRUCK SCHEDULING PROBLEM ⋮ The \(k\)-server problem with advice in \(d\) dimensions and on the sphere ⋮ Tight bounds for double coverage against weak adversaries ⋮ On the Additive Constant of the k-Server Work Function Algorithm ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ Nested convex bodies are chaseable ⋮ 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 ⋮ Online computation with advice ⋮ Online matching on a line ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ A lower bound on the competitivity of memoryless algorithms for a generalization of the CNN problem ⋮ A Randomized Algorithm for Two Servers in Cross Polytope Spaces ⋮ On page migration and other relaxed task systems ⋮ Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers ⋮ 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 ⋮ Greedy metric minimum online matchings with random arrivals ⋮ Managing multiple mobile resources ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Unnamed Item ⋮ Stochastic dominance and the bijective ratio of online algorithms ⋮ Multi-Finger Binary Search Trees ⋮ Better Bounds for Online Line Chasing ⋮ A Combinatorial Metrical Task System Problem Under the Uniform Metric ⋮ Unnamed Item ⋮ Competitive analysis of randomized paging algorithms ⋮ Randomized algorithm for the \(k\)-server problem on decomposable spaces ⋮ The traveling \(k\)-median problem: approximating optimal network coverage ⋮ The online \(k\)-server problem with rejection ⋮ On list update and work function algorithms. ⋮ The 3-server problem in the plane. ⋮ A randomized algorithm for two servers on the line. ⋮ A general decomposition theorem for the \(k\)-server problem ⋮ Asymptotically optimal online page migration on three points ⋮ Trackless online algorithms for the server problem ⋮ Memoryless algorithms for the generalized k-server problem on uniform metrics
This page was built for publication: On the k -server conjecture
