Research Interests : Algorithms, Information Technology Modeling, Network Design and Analysis, Optimization
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)
WILLIAMSON, DAVID P. 