publication . Article . 2002

more on random walks electrical networks and the harmonic k server algorithm

Yair Bartal; Marek Chrobak; John Noga; Prabhakar Raghavan;
Restricted
  • Published: 07 Oct 2002 Journal: Information Processing Letters, volume 84, pages 271-276 (issn: 0020-0190, Copyright policy)
  • Publisher: Elsevier BV
Abstract
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 ½n(n - 1). Both bounds are tight. As a consequence, we obtain that the harmonic algorithm for the k server problem is ½k(k + 1)-com...
Subjects
free text keywords: Signal Processing, Theoretical Computer Science, Information Systems, Computer Science Applications, Vertex (graph theory), Random walk, K-server problem, Upper and lower bounds, Admittance parameters, Discrete mathematics, Mathematics, Stretch factor, Triangle inequality, Complete graph, Combinatorics, Algorithm
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue