Computer Science Colloquium
Geometric Optics, Linear Programming and Congestion in Sensornets
Richard M. Karp
University of California at Berkeley
Friday, January 27, 2006 11:30 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185
Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html
Zvi Kedem firstname.lastname@example.org, (212) 998-3101
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.
| contact email@example.com