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

DOI10.1016/S0020-0190(02)00287-9zbMath1042.68052OpenAlexW2029198432WikidataQ57904545 ScholiaQ57904545MaRDI QIDQ1853151

Prabhakar Raghavan, Marek Chrobak, John Noga, 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)

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

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