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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (1.98 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 3 (July 1993) table of contents

Pages: 421 - 453

Year of Publication: 1993

ISSN:0004-5411

Authors

Don Coppersmith	IBM T. J. Watson Research Center, Yorktown Heights, New York
Peter Doyle	AT&T Bell Laboratories, Marray Hill, New Jersey
Prabhakar Raghavan	IBM T. J. Watson Research Center, Yorktown Heights, New York
Marc Snir	IBM T. J. Watson Research Center, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 104, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174130.174131 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	~BAEZA-YATES, R. A., CULBERSON, J. C., AND RAWLINS, G. J.E. Searching with uncertainty. ~Tech. Rep. CS-87-68. Comput. Scl. Dept., Univ. of Waterloo, Waterloo, Ont., Canada, Oct. ~1987.
	2	~BAUM, L. E., AND EAGON, J.A. An inequality with applications to statistical estimation for ~probabilistic functions of Markov processes and to a model for ecology. Bull. Amer. Math. Soc. ~73 (1967), 360-363.
	3	S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
	4	P. Berman , H. Karloff , G. Tardos, A competitive 3-server algorithm, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.280-290, January 22-24, 1990, San Francisco, California, United States
	5	A. Borodin , N. Linial , M. Saks, An optimal online algorithm for metrical task systems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.373-382, January 1987, New York, New York, United States [doi>10.1145/28395.28435]
	6	~BOTr, R., AND DUFFIN, R.J. On the algebra of networks. Trans. Amer Math. Soc. 74 (1953), ~99-109.
	7	A. K. Chandra , P. Raghavan , W. L. Ruzzo , R. Smolensky, The electrical resistance of a graph captures its commute and cover times, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.574-586, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73062]
	8	M. Chrobak , H. Karloff , T. Payne , S. Vishwanathan, New results on server problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.291-300, January 22-24, 1990, San Francisco, California, United States
	9	Marek Chrobak , Lawrence L. Larmore, An optimal on-line algorithm for K-servers on trees, SIAM Journal on Computing, v.20 n.1, p.144-148, Feb. 1991 [doi>10.1137/0220008]
	10	~DOYLE, P. G., AND SNELL, J.k. Random Walks and Electric Networks'. The Mathematical ~Association of America, Providence, R.I., 1984.
	11	Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
	12	~FIAT, A., RABANI, Y., AND RAVID, Y. Competitive k-server algorithms. In Proceedings of the ~31st Annual IEEE S?npostum on Foutldatzons of Computer Science. ItEEE, New York, 1990, ~pp. 454-463.
	13	~FOSTER, R.M. The average impedance of an electrical network In Contnbz~tions to Applied ~Mechanics (Reissner Annzversary l/ohtme). Edwards Bros., Ann Arbor, Mich., 1949, pp. ~333-340.
	14	~FOSTER, R. M. An extension of a network theorem. IRE Trans. Ctrcult Theory 8 (1961), ~75-76.
	15	E. F. Grove, The harmonic online K-server algorithm is competitive, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.260-266, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103448]
	16	~KARLIN, A. R., MANASSE, M. S., RUDOLPH, L., AND SLEATOR, D. m. Competitive snoopy ~caching. Algorithmica 3, 1 (1988), 70-119.
	17	~KEMENY, J. G., SNELL, J. L., AND KNAPP, A. W. Denumerable Markov Chains. In The ~Unwersity Series m Higher Mathematics. Van Nostrand, Princeton, N.J., 1966.
	18	Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
	19	~MARSHALL, A. W., AND OLKIN, I. hlequalities: Theo.rv of Majorization and Its Apphcations. ~Academic Press, Orlando, Fla., 1979.
	20	Christos H. Papadimitriou , Mihalis Yannakakis, Shortest Paths Without a Map, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.610-620, July 11-15, 1989
	21	Prabhakar Raghavan , Marc Snir, Memory Versus Randomization in On-line Algorithms (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.687-703, July 11-15, 1989
	22	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	23	~WEINBERG, L. Network Analysis and Synthesis. McGraw-Hill, New York, 1962.

CITED BY 9

	Elias Koutsoupias , Christos H. Papadimitriou, On the k-server conjecture, Journal of the ACM (JACM), v.42 n.5, p.971-983, Sept. 1995
	Tyng-Ruey Chuang , Wen L. Hwang, A probabilistic approach to the problem of automatic selection of data representations, ACM SIGPLAN Notices, v.31 n.6, p.190-200, June 15, 1996
	Prasad Tetali, Design of on-line algorithms using hitting times, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.402-411, January 23-25, 1994, Arlington, Virginia, United States
	Enoch Peserico, The lazy adversary conjecture fails, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Yair Bartal , Marek Chrobak , John Noga , Prabhakar Raghavan, More on random walks, electrical networks, and the harmonic k-server algorithm, Information Processing Letters, v.84 n.5, p.271-276, 16 December 2002
	Marek Chrobak , Jiří Sgall, The weighted 2-server problem, Theoretical Computer Science, v.324 n.2-3, p.289-312, 20 September 2004
	Marek Chrobak, SIGACT news online algorithms column 2, ACM SIGACT News, v.35 n.1, March 2004
	Mihyun Kang, Efficiency test of pseudorandom number generators using random walks, Journal of Computational and Applied Mathematics, v.174 n.1, p.165-177, 1 February 2005
	Jens Vygen, New theoretical results on quadratic placement, Integration, the VLSI Journal, v.40 n.3, p.305-314, April, 2007