On the Integrality Gap of the Subtour LP for the 1,2-TSP
Jiawei Qian, Frans Schalekamp, David P. Williamson, and Anke van Zuylen
Mathematical Programming, to appear.
2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
Frans Schalekamp, David P. Williamson, and Anke van Zuylen
Mathematics of Operations Research 39:403-417, 2014.
On Some Recent Approximation Algorithms for MAX SAT
Matthias Poloczek, David P. Williamson, and Anke van Zuylen
In Alberto Pardo and Alfredo Viola, editors, Lecture Notes in Computer Science Number 8392, LATIN 2014: Theoretical Informatics, pages 589-609, 2014.
A Simple, Greedy Approximation Algorithm for MAX SAT
DIMACS Workshop in Honor of Alan Hoffman, Rutgers University. Piscataway, NJ, USA.
September 20, 2014.
The Traveling Salesman Problem: An Overview
Ebay Research. San Jose, CA, USA.
January 21, 2014.
The Rank Aggregation Problem
InWeb Workshop, Universidade Federal de Minas Gerais. Belo Horizonte, Brazil.
December 10, 2012.
David P. Williamson is a Professor at Cornell University in the School of Operations Research and Information Engineering.
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 (Assistant Professor, William and Mary Math)
- Chandrashekhar Nagarajan, August 2008 (Facebook)
- Yogeshwer Sharma, August 2010 (Facebook)
- Jiawei Qian, December 2011 (Bank of America)
His current Ph.D. students are:
- James Davis
- Alice Paul
- Sin-Shuen Cheung