The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Design of On-Line Algorithms Using Hitting Times
Prasad Tetali,
Pages. 1232-1246
Abstract
Contents 1. Introduction
2. Results on ergodic Markov chains
2.1. Synthesis of an ergodic walk
2.2. A trace inequality
3. Lower and upper bounds on stretch
4. $k$-servers with asymmetric costs
5. Task systems
5.1. Lower and upper bounds
5.2. Memoryless counterpart
6. Loose ends
Key words random walk, graph, Markov chain, reversibility, competitive ratio, first passage time, M-matrices
Mathmatical Subject Classification 68Q25, 60C05, 60J10, 60J15, 60