Random walks on weighted graphs and applications to on-line algorithms

摘要: We study the design and analysis of randomized on-line algorithms. show that this problem is closely related to synthesis random walks on graphs with positive real costs their edges. develop a theory for such walks, employ it competitive IBM T.J. Watson Research Center, Yorktown Heights, NY 10598. ATT cij = cji > 0 cost edge connecting vertices i j, cii 0. Consider walk graph G, executed according transition probability matrix P (pij); pij moves from vertex pays in step. Let eij (not general equal eji) be expected starting at ending j (eii round trip i). say has stretch c if there exists constant that, any sequence i0, i1, . , il ∑l j=1 eij−1ij ≤ · cij−1ij + a. prove following tight result: Any weighted n least − 1, every n− 1. The upper bound proof constructive, shows how compute C (cij). uses new connections between effective resistances networks resistors, together results electric network theory. resistors vertices, conductance σij (vertices are connected by resistor branch resistance 1/σij). Rij (i.e., 1/Rij current would flow one volt were applied j; known ≥ σij). resistive defined probabilities σij/ ∑ k σik. In Section 3 we 1 Rij. Thus, optimal obtained computing inverse (σij) (cij): conductances (σij 0), so i, branch)