An Optimal On-Line Algorithm for K Servers on Trees

DOI10.1137/0220008zbMath0716.68038OpenAlexW2086989193WikidataQ63198877 ScholiaQ63198877MaRDI QIDQ3204037

Lawrence L. Larmore, Marek Chrobak

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/d5072f10b3f9e98710085709d91879793caf4890

zbMATH Keywords

metric spacecompetitive analysison-line algorithmtreesthe server problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (49)

Competitive randomized algorithms for nonuniform problems ⋮ A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle ⋮ Competitive \(k\)-server algorithms ⋮ The list update problem and the retrieval of sets ⋮ Competitive algorithms for the weighted server problem ⋮ A better lower bound on the competitive ratio of the randomized 2-server problem ⋮ The weighted 2-server problem ⋮ On the competitive ratio of the work function algorithm for the \(k\)-server problem ⋮ The CNN problem and other \(k\)-server variants ⋮ The 2-evader problem ⋮ Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications ⋮ Randomized competitive analysis for two server problems ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ The minimum backlog problem ⋮ R-LINE: a better randomized 2-server algorithm on the line ⋮ Breaking the 2-competitiveness barrier for two servers in a tree ⋮ 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 ⋮ Unnamed Item ⋮ Competitive algorithms for the bicriteria \(k\)-server problem ⋮ The \(k\)-server problem ⋮ Randomized Competitive Analysis for Two-Server Problems ⋮ ON THE k-TRUCK SCHEDULING PROBLEM ⋮ A note on the server problem and a benevolent adversary ⋮ Dynamic pricing of servers on trees ⋮ Geometric two-server algorithms ⋮ Tight bounds for double coverage against weak adversaries ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ 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 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 ⋮ Online facility assignment ⋮ On page migration and other relaxed task systems ⋮ 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 ⋮ Competitive analysis of randomized paging algorithms ⋮ The fast algorithm for online \(k\)-server problem on trees ⋮ 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 ⋮ The online \(k\)-server problem with max-distance objective ⋮ On-line algorithms for locating checkpoints ⋮ On Advice Complexity of the k-server Problem under Sparse Metrics ⋮ Trackless online algorithms for the server problem

This page was built for publication: An Optimal On-Line Algorithm for K Servers on Trees