Feed: Scribd Feed
Posted on: Thursday, February 04, 2010 7:01 PM
Author: Scribd Feed
Subject: Math_On-Line Algorithms Application
| Random Walks on Weighted Graphs, and Applications to On-line Algorithms Don Coppersmith* Peter Doyley Prabhakar Raghavan* Marc Snir* Abstract We study the design and analysis of randomized on-line algorithms. We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges. We develop a theory for the synthesis of such walks, and employ it to design competitive on-line algorithms. * y IBM T.J. Watson Research Center, Yorktown Heights, NY 10598. AT&T Bell Laboratories, Murray Hill, NJ 07974. 1 *1 Overview Much recent work has d |
No comments:
Post a Comment