Design of On-Line Algorithms Using Hitting Times

DOI10.1137/S0097539798335511zbMath0939.68046OpenAlexW1973108190MaRDI QIDQ4268706

Prasad Tetali

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539798335511

zbMATH Keywords

graphcompetitive ratioMarkov chainrandom walkfirst passage timereversibilityM-matrices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Stochastic matrices (15B51)

Related Items (4)

Transition matrices for well-conditioned Markov chains ⋮ Efficiency test of pseudorandom number generators using random walks ⋮ Random walks on a finite graph with congestion points ⋮ Improved approximation of the minimum cover time

This page was built for publication: Design of On-Line Algorithms Using Hitting Times