Computer Science Colloquium
Internet Algorithmics and Approximations
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: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html
Richard Colecole@cs.nyu.edu, (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.
| contact firstname.lastname@example.org