Computer Science Colloquium

Internet Algorithmics and Approximations

Lisa Fleischer
IBM T.J. Watson Research Center

Thursday, April 27, 2006 2:00 P.M.
Room 109 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Colloquium Information:


Richard, (212) 998-3119


The Internet is a huge and complex environment that gives rise to many optimization problems. Even simplified versions of these problems are frequently provably hard to solve exactly; and the size and decentralized nature of the system prevents brute-force approaches. Approximation algorithms produce provably good solutions quickly, no matter what the instance. This is useful not only to generate real-time solutions, but also to provide good bounds and help prune the search space for more comprehensive searches for better solutions.

We describe some of our recent research to provide provable guarantees for a few different Internet-inspired design problems. These problems include rank aggregation, congestion control, network design with economies of scale, and design for uncertain demand.

top | contact