Algorithms, Information Technology Modeling, Network Design and Analysis, Optimization

Office: 236 Rhodes

Phone: 607.255.4883

Website: click here

Fax: 607.255.9129

David Williamson received his Ph.D. in computer science from M.I.T. in 1993. He joined Cornell University in 2004 with a joint appointment with the School of Operations Research and Industrial Engineering and Computer and Information Science (CIS). Before joining Cornell, Williamson was the Senior Manager of the Computer Science Principles and Methodologies Department at the IBM Almaden Research Center. From 1995 - 2000 he was a Research Staff Member at IBM T.J. Watson Research Center. He was also an Adjunct Professor at Columbia University and Cornell University in 1998, as well as a lecturer at MIT in 2000 and at Stanford in 2003.

His primary research interest has been in the design and analysis of polynomial time algorithms for the approximate solution of hard problems in discrete optimization, especially problems arising in network design, scheduling, facility, location, and routing. He focuses on the use of techniques from the area of mathematical programming for designing such algorithms, including such techniques as the primal–dual method and semidefinite programming.

Selected Publications

“Approximation algorithms for MAX 3-CUT and other problems via complex semidefinite programming.” Journal of Computer and System Sciences 68: 442 - 470 (2004). (With M.X. Goemans)

“A Faster, Better Approximation Algorithm for the Minimum Latency Problem”. Preliminary version appeared in Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms ( 2003). (With A. Archer and A. Levin)

“Searching the Workplace Web”. Proceedings of the 12th Annual World-Wide Web Conference (2003). (With R. Fagin, R. Kumar, K. McCurley, J. Novak, D. Sivakumar, and J. Tomlin)

“The Primal-Dual Method for Approximation Algorithms”. Mathematical Programming B 91: 447 - 478 (2002).

“An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem”. Proceedings of the 42nd Annual IEEE Symposium on the Foundations of Computer Science (2001). (With L. Fleischer and K. Jain)

Lectures

“A general method for incremental approximation and hierarchical clustering,” IIT Delhi Workshop on Approximation Algorithms, October 2005.

“Finding provably near-optimal solutions to discrete optimization problems,” University of Illinois at Urbana-Champaign, March 2005.

Professional Activities

Area Editor , Discrete Optimization, Mathematics of Operations Research

Associate Editor , ACM Transactions on Algorithms

Associate Editor, SIAM Journal on Computing

Associate Editor, SIAM Journal on Discrete Mathematics

University Activities

Director of Undergraduate Studies, Information Science, Fall 2005 - present

Awards and Recognition

AMS-MPS Fulkerson Prize for outstanding paper in discrete mathematics, 2000

1999 SIAM Group, Optimization Prize for outstanding paper in optimization, 1996 - 1999