On traversing layered graphs on-line

Ramesh, H. (1995) On traversing layered graphs on-line Journal of Algorithms, 18 (3). pp. 480-512. ISSN 0196-6774

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1006/jagm.1995.1019


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.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:102238
Deposited On:09 Mar 2018 11:20
Last Modified:09 Mar 2018 11:20

Repository Staff Only: item control page