**December 9, 2005: Seminar: Richard Karp ''Geometric Optics, Linear Programming and Congestion in Sensornets''**

University of California, Berkeley

Friday, December 9, 2005

11:00am, 1043 ERF

We consider the problem of routing in a geographically distributed network of processors to minimize the maximum congestion at any node, or to optimize the trade-off between average path delay and maximum congestion. Instead of assuming a discrete model with nodes at known positions, we assume that the density of nodes is so large that we can adopt a continuous model, in which each communication path is a continuous curve in a region of the plane and congestion at a point corresponds to the limiting density of paths in a neighborhood of the point. Using an argument based on linear programming, we show that the problem is isomorphic to a problem in geometric optics, in which we interpret the communication paths as the minimum-time paths followed by light rays in a medium where the speed of light varies continuously. Our problem is then to specify the speed of light as a function of position so that the resulting minimum-time paths minimize maximum congestion. Once this function has been specified the computation of minimum- time paths is a standard problem in the calculus of variations, but the problem of specifying the function is novel, and we give an approach based on the primal-dual algorithm of linear programming. The discussion will be accessible without requiring knowledge of calculus of variations or linear programming. Joint work with Christos Papadimitriou, Lucian Popa and Afshin Rostami.

Richard Karp won the ACM Turing Award in 1985. He is a member of the National Academy of Sciences and an ACM Fellow.

University of Illinois at Chicago | College of Engineering

Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu |
WISEST Helping Women Faculty Advance Funded by NSF |