More on random walks, electrical networks, and the harmonic k-server algorithm.

DOI10.1016/S0020-0190(02)00287-9zbMATH Open1042.68052OpenAlexW2029198432WikidataQ57904545 ScholiaQ57904545MaRDI QIDQ1853151FDOQ1853151

Authors Marek Chrobak, J. Noga, Prabhakar Raghavan, Yair Bartal

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00287-9

zbMATH Keywords

Analysis of algorithmsTheory of computationRandomizationElectrical networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1962818
• The harmonic k -server algorithm is competitive
• A simple analysis of the harmonic algorithm for two servers
• Randomized k-server algorithms for growth-rate bounded graphs
• scientific article; zbMATH DE number 6469207

Cites work

• scientific article; zbMATH DE number 3167398 (Why is no real title available?)
• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• A simple analysis of the harmonic algorithm for two servers
• HARMONIC is 3-competitive for two servers
• Random walks on weighted graphs and applications to on-line algorithms
• The harmonic k -server algorithm is competitive

Cited in

(6)

• Further results on the expected hitting time, the cover cost and the related invariants of graphs
• Expected hitting times for random walks on the diamond hierarchical graphs involving some classical parameters
• Dumbbell graphs with extremal (reverse) cover cost
• The \(k\)-server problem
• Expected hitting times for random walks on quadrilateral graphs and their applications
• Expected hitting times for random walks on the \(k\)-triangle graph and their applications

This page was built for publication: More on random walks, electrical networks, and the harmonic \(k\)-server algorithm.

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