On traversing layered graphs on-line

Abstract

The following bounds on the competitive ratios of deterministic and randomized on-line algorithms for traversing width-w layered graphs are obtained. A deterministic algorithm with a competitive ratio of (2). This ratio is close to the lower bound of Ω(2) and improves upon the previous best upper bound of (9). The first known polynomially competitive randomized. algorithm with a competitive ratio of (). This settles a conjecture due to Fiat. (A. Fiat, D. P. Foster, H. Karloff, V. Rabani, Y. Ravid and S. Vishwanathan, "Proceedings 32nd Annual Symposium on Foundations of Computer Science, Sept. 1991). A lower bound of Ω()/(log)) on the competitive ratio of any randomized algorithm for this problem, where ε is any positive number. The previous best lower bound was linear.