An Optimal On-Line Algorithm for K Servers on Trees

DOI10.1137/0220008zbMATH Open0716.68038DBLPjournals/siamcomp/ChrobakL91OpenAlexW2086989193WikidataQ63198877 ScholiaQ63198877MaRDI QIDQ3204037FDOQ3204037

Authors: 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

Recommendations

• The fast algorithm for online \(k\)-server problem on trees
• A randomized on–line algorithm for the k–server problem on a line
• On online algorithms with advice for the \(k\)-server problem
• On online algorithms with advice for the \(k\)-server problem
• A fast implementation of the optimal off-line algorithm for solving the \(k\)-server problem
• The \((h,k)\)-server problem on bounded depth trees
• The (h, k)-Server Problem on Bounded Depth Trees
• scientific article; zbMATH DE number 1559551
• An online algorithm for the dynamic maximal dense tree problem
• The online \(k\)-server problem with max-distance objective

zbMATH Keywords

treescompetitive analysismetric spaceon-line algorithmthe server problem

Mathematics Subject Classification ID

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

Cited In (56)

• Breaking the 2-competitiveness barrier for two servers in a tree
• The k-Server Problem with Delays on the Uniform Metric Space
• Deterministic 3-server on a circle and the limitation of canonical potentials
• Time efficient implementation for online \(k\)-server problem on trees
• Online paging with heterogeneous cache slots
• On-line algorithms for locating checkpoints
• ON THE k-TRUCK SCHEDULING PROBLEM
• \(k\)-servers with a smile: online algorithms via projections
• A Randomized Algorithm for Two Servers in Cross Polytope Spaces
• Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications
• Tight bounds for double coverage against weak adversaries
• A better lower bound on the competitive ratio of the randomized 2-server problem
• Online \(k\)-taxi via double coverage and time-reverse primal-dual
• The (h, k)-Server Problem on Bounded Depth Trees
• More on randomized on-line algorithms for caching.
• The \(k\)-resource problem in uniform metric spaces
• The CNN problem and other \(k\)-server variants
• On advice complexity of the \(k\)-server problem under sparse metrics
• Randomized Competitive Analysis for Two-Server Problems
• Title not available (Why is that?)
• The \(k\)-server problem
• Stochastic dominance and the bijective ratio of online algorithms
• Metrical service systems with multiple servers
• Trackless online algorithms for the server problem
• R-LINE: a better randomized 2-server algorithm on the line
• The minimum backlog problem
• Competitive Algorithms for Generalized k -Server in Uniform Metrics
• Multi-Finger Binary Search Trees
• Competitive randomized algorithms for nonuniform problems
• The 2-evader problem
• Dynamic pricing of servers on trees
• Competitive analysis of randomized paging algorithms
• Title not available (Why is that?)
• A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle
• Online \(k\)-taxi via double coverage and time-reverse primal-dual
• Geometric two-server algorithms
• A note on the server problem and a benevolent adversary
• A lower bound on the competitivity of memoryless algorithms for a generalization of the CNN problem
• Competitive \(k\)-server algorithms
• Online facility assignment
• A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs
• A randomized algorithm for two servers on the line.
• The 3-server problem in the plane.
• On the competitive ratio of the work function algorithm for the \(k\)-server problem
• A general decomposition theorem for the \(k\)-server problem
• The weighted 2-server problem
• On the advice complexity of the \(k\)-server problem under sparse metrics
• A randomized algorithm for two servers in cross polytope spaces
• Randomized competitive analysis for two server problems
• The list update problem and the retrieval of sets
• The online \(k\)-server problem with max-distance objective
• On page migration and other relaxed task systems
• Competitive algorithms for the weighted server problem
• The fast algorithm for online \(k\)-server problem on trees
• Competitive algorithms for the bicriteria \(k\)-server problem
• Competitive analysis of on-line disk scheduling

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3204037)