Three applications of dynamic programming to network management

Abstract: Dynamic programming is an algorithmic technique with a wide
variety of applications, from operations research to formal languages.
Even when it does not solve a problem completely, it can be useful as part
of an overall approach. In this talk I describe three different network
problems where I was able to exploit it, the work being done in collaborations
with more systems-oriented researchers at AT&T: (1) using caches for
content distribution, (2) mapping IP addresses to autonomous systems,
and (3) optimizing access control lists in routers.
David S. Johnson is Head of the Algorithms and Optimization Department
at AT&T Labs-Research in Florham Park, NJ, and has been a researcher
at the Labs (in its many incarnations) since 1973, when he received
his Ph.D from MIT.

The author of over 100 technical papers, he is perhaps best known as the
co-author of COMPUTERS AND INTRACTABILITY: A GUIDE TO THE THEORY OF
NP-COMPLETENESS, for which he shared the Lanchester Prize of the
Operations Research Society of America (1979). His research interests
(in addition to the theory of NP-completeness) include approximation
algorithms for combinatorial problems, and the experimental analysis
of algorithms, with special emphasis on bin packing, graph coloring,
and the traveling salesman problem. As one of the founders of ACM's
Kanellakis Prize, he is particularly interested in recognizing and
encouraging the interaction between theory and practice in computer science.