More on random walks, electrical networks, and the harmonic \(k\)-server algorithm.
type: Item
instance of: scholarly article
title: More on random walks, electrical networks, and the harmonic \(k\)-server algorithm.
zbMATH Open document ID: 1042.68052
DOI: 10.1016/S0020-0190(02)00287-9
author: Marek Chrobak
author: J. Noga
author: Prabhakar Raghavan
author: Yair Bartal
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: Techniques from electrical network theory have been used to establish various properties of random walks. We explore this connection further, by showing how the classical formulas for the determinant and cofactors of the admittance matrix, due to Maxwell and Kirchoff, yield upper bounds on the edge stretch factor of the harmonic random walk. For any complete, \(n\)-vertex graph with distances assigned to its edges, we show the upper bound of \((n-1)^{2}\). If the distance function satisfies the triangle inequality, we give the upper bound of \(\frac12n(n-1)\). Both bounds are tight. As a consequence, we obtain that the harmonic algorithm for the \(k\) server problem is \(\frac12k(k+1)\)-competitive against the lazy adversary.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1856487
zbMATH Keywords: Analysis of algorithms
zbMATH Keywords: Theory of computation
zbMATH Keywords: Randomization
zbMATH Keywords: Electrical networks
Wikidata QID: Q57904545
MaRDI profile type: Publication
cites work: The harmonic k -server algorithm is competitive
cites work: Q4223058
cites work: HARMONIC is 3-competitive for two servers
cites work: A simple analysis of the harmonic algorithm for two servers
cites work: Random walks on weighted graphs and applications to on-line algorithms
cites work: Q3706275
cites work: Q3285875
full work available at URL: s0020-0190(02)00287-9
OpenAlex ID: W2029198432
description: scientific article; zbMATH DE number 1856487