David P. Williamson
School of Operations Research and Industrial Engineering

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.


Recent papers Theses
  • On the Design of Approximation Algorithms for a Class of Graph Problems, PhD thesis, MIT Computer Science, September 1993.
  • Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem, Master's thesis, MIT Computer Science, June 1990. [PDF 2.0MB]
Maximum cut and satisfiability problems Network design problems Scheduling Feedback vertex set problems


  • The approximability of constraint satisfaction, with Sanjeev Khanna and Madhu Sudan. SIAM Journal on Computing 30:1863-1920, 2001.
  • Gadgets, Approximation, and Linear Programming, with Luca Trevisan, Greg Sorkin, and Madhu Sudan. SIAM Journal on Computing  29:2074-2097, 2000.
  • Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout , with Alok Aggarwal and Jon Kleinberg. SIAM Journal on Computing 29:1321-1333, 2000.
  • Adversarial Queueing Theory, with Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, and Madhu Sudan. JACM 48:13-38, 2001.
  • On the Number of Small Cuts in a Graph, with Monika Rauch Henzinger. Information Processing Letters, 59:41-44, 1996.

Course Notes




Selected Publications

DPW Home

Cornell ORIE

Cornell CIS