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 100121185
Directions: http://cs.nyu.edu/csweb/Location/directions.html
Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html
Hosts:
Zvi Kedem kedem@cs.nyu.edu, (212) 9983101
Abstract
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 tradeoff 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 minimumtime 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 minimumtime paths minimize maximum congestion. Once this function has been specified the computation of minimumtime 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 primaldual 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.
top  contact webmaster@cs.nyu.edu
