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

The University of Illinois at Chicago

Department of Computer Science

2005-2006 Distinguished Lecturer Seminar Series

"Geometric Optics, Linear Programming and Congestion in Sensornets"

Richard Karp
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.

Host: Professor Robert Sloan

Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF