Recent Publications
-
A proof of the Boyd-Carr conjecture
Frans Schalekamp, David P. Williamson, and Anke van Zuylen
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1477-1486, 2012.
-
A note on the generalized min-sum set cover problem
Martin Skutella and David P. Williamson
Operations Research Letters 39:433-436, 2011.
-
On the integrality gap of the Subtour LP for the 1,2-TSP
Jiawei Qian, Frans Schalekamp, David P. Williamson, and Anke van Zuylen
To appear in LATIN 2012.
Recent Talks
-
The Subtour LP for the Traveling Salesman Problem
5th International Conference on High Performance Scientific Computing (HPSC 2012). Hanoi, Vietnam.
March 06, 2012.
-
What Computers Can Compute (Approximately)
University of Hawaii. Honolulu, HI, USA.
January 06, 2012.
-
The Subtour LP for the Traveling Salesman Problem
Cornell University. Ithaca, NY, USA.
November 22, 2011.
David P. Williamson is a Professor at Cornell University with a joint appointment in the School of Operations Research and Information Engineering and the Department of Information Science.
He received his Ph.D. in Computer Science from MIT under Professor Michel X. Goemans in 1993. After a postdoc at Cornell under Professor Éva Tardos, he was a Research Staff Member for IBM Research at the T.J. Watson Research Center in Yorktown Heights, New York. From 2000 to 2003, he was the Senior Manager of the Computer Science Principles and Methodologies group at IBM's Almaden Research Center in San Jose, California. He moved to Cornell University in 2004.
His research focuses on finding efficient algorithms for hard discrete optimization problems, with a focus on approximation algorithms for problems in network design, facility location, and scheduling. Other interests include algorithms for information networks.
His graduated Ph.D. students are:
- Anke van Zuylen, June 2008 (Postdoc, MPI Saabrücken)
- Chandrashekhar Nagarajan, August 2008 (Yahoo!)
- Yogeshwer Sharma, August 2010 (Facebook)
His current Ph.D. students are:
- Jiawei Qian