Fifth Annual Paris C. Kanellakis Memorial Lecture

"Geometric Optics, Linear Programming and Congestion in Sensornets"

Richard Karp, UC Berkeley

Thursday, December 8, 2005 at 4:00 P.M.

Room 368 (CIT 3rd Floor)

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.

This is joint work with Christos Papadimitriou, Lucian Popa and Afshin Rostami.

Series:

This lecture series honors Paris Kanellakis, a distinguished computer scientist who was an esteemed and beloved member of the Brown Computer Science department. Paris joined the Computer Science Department in 1981 and became a full professor in 1990. His research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, the principles of distributed computing and combinatorial optimization. He died in an airplane crash on December 20, 1995, along with his wife, Maria Teresa Otoya, and their two young children, Alexandra and Stephanos Kanellakis.

Host: Philip Klein