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 (799 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 369 - 378

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

D. Coppersmith	IBM T.J. Watson Research Center, Yorktown Heights, NY
P. Doyle	AT&T Bell Laboratories, Murray Hill, NJ
P. Raghavan	IBM T.J. Watson Research Center, Yorktown Heights, NY
M. Snir	IBM T.J. Watson Research Center, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 25, Citation Count: 10

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/100216.100266 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	L.E. Baum and J.A. Eagon. An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull. Amer. Math. Soc., 73:363-363, 1967.
	2	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]
	3	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
	4	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]
	5	R. Bott and R. J. Duffin. On the algebra of networks. Trans. Amer. Math. Soc., 74:99-109, 1953.
	6	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]
	7	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
	8	M. Chrobak and L.L. Larmore. An optimal online algorithm for k servers on trees. Submitted for publication, 1989.
	9	P.G. Doyle and J.L. Snell. Random Walks and Electric Networks. The Mathematical Association of America, 1984.
	10	A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, and N. Young. On competitive algorithms for paging problems. To appear in Journal of Algorithms, 1988.
	11	R. M. Foster. The average impedance of an electrical network. In Contributions to Applied Mechanics (Reissner Anniversary Volume), pages 333-340. Edwards Bros., Ann Arbor, Mich., 1949.
	12	R. M. Foster. An extension of a network theorem. IRE Trans. Circuit Theory, 8:75-76, 1961.
	13	J.G. Kemeny, J. L. Snell, and A.W. Knapp. Denumerable Markov Chains. The University Series in Higher Mathematics. Van Nostrand, Princeton, NJ, 1966.
	14	Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62243]
	15	A. W. Marshall and I. Olkin. Inequalities: Theory of Majorization and lts Applications. Academic Press, New York, 1979.
	16	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
	17	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
	18	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]
	19	L. Weinberg. Network Analysis and Synthesis. McGraw-Hill, New York, 1962.

CITED BY 10

	Prasad Tetali , Peter Winkler, On a random walk problem arising in self-stabilizing token management, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.273-280, August 19-21, 1991, Montreal, Quebec, Canada
	Sandy Irani , Nick Reingold , Jeffery Westbrook , Daniel D. Sleator, Randomized competitive algorithms for the list update problem, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.251-260, January 28-30, 1991, San Francisco, California, United States
	Neal Young, On-line caching as cache size varies, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 28-30, 1991, San Francisco, California, United States
	Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992
	Marek Chrobak , Lawrence L. Larmore, Generosity helps, or an 11–competitive algorithm for three servers, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.196-202, September 1992, Orlando, Florida, United States
	Bala Kalyanasundaram , Kirk Pruhs, On-line weighted matching, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.234-240, January 28-30, 1991, San Francisco, California, United States
	M. Bern , D. H. Greene , A. Raghunathan , M. Sudan, Online algorithms for locating checkpoints, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.359-368, May 13-17, 1990, Baltimore, Maryland, United States
	Xiaotie Deng , Sanjeev Mahajan, Infinite games: randomization, computability, and applications to online problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.289-298, May 05-08, 1991, New Orleans, Louisiana, United States
	Allan Borodin, Can competitive analysis be made competitive?, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
	Gianluca De Marco , Luisa Gargano , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc , Ugo Vaccaro, Asynchronous deterministic rendezvous in graphs, Theoretical Computer Science, v.355 n.3, p.315-326, 14 April 2006