Message-Passing Algorithms for Nonserial Dynamic Programming
<-- Return to the list
Date: 10-10-2006
Start Time:
1:00pm
End Time: 2:00pm
Speaker: Ben Van Roy, Stanford University
Location: Uris 333
Abstract
Consider an optimization problem in which decision variables are associated with vertices of a sparse undirected graph and the objective function is a sum of component functions, each of which depends only on the subset of variables associated with a clique. So-called nonserial dynamic programs appear in a broad array of important applications. However, the class of problems is computationally intractable, even when variables are binary and cliques small.
Message-passing algorithms, which generalize the value iteration algorithm of dynamic programming, have proved to be effective solution methods for nonserial dynamic programs arising in error correcting codes and satisfiability problems. This talk will cover some history, recent experience with facility location and distributed averaging, and theoretical results about convergence and resulting solutions.
Bio
Benjamin Van Roy is an associate professor of management science and engineering, electrical engineering, and, by courtesy, computer science, at Stanford University, where he has been since 1998. He received the S.B. in computer science and engineering and the S.M. and Ph.D. in electrical engineering and computer science, all from MIT. He is a member of INFORMS and IEEE. He serves on the editorial boards of Discrete Event Dynamic Systems, Machine Learning, Mathematics of Operations Research. He has received several awards; among them are the Stanford Tau Beta Pi Award for Excellence in Undergraduate Teaching, the NSF CAREER Award, and the MIT George M. Sprowls Dissertation Award.