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

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

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

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

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

zbMATH Keywords

Analysis of algorithmsTheory of computationRandomizationElectrical networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Random walks on weighted graphs and applications to on-line algorithms
• HARMONIC is 3-competitive for two servers
• A simple analysis of the harmonic algorithm for two servers
• The harmonic k -server algorithm is competitive
• Title not available (Why is that?)

Cited In (6)

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