Network Flow Algorithms
David P. Williamson
To be published by Cambridge University Press, Fall 2019.
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
Samuel C. Gutekunst and David P. Williamson
Tight Bounds for Online Weighted Tree Augmentation
Joseph (Seffi) Naor, Seeun William Umboh, and David P. Williamson
In Christel Baier, Ioannis Chatzigiannakis, Paola Flochinni, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 88:1-88:14, 2019.
Semidefinite Programming Relaxations of the Traveling Salesman Problem
University of Massachusetts Amherst, Discrete Math Seminar. Amherst, MA, USA.
October 24, 2018.
Vector Representations of Graphs and the Maximum Cut Problem
University of California at Berkeley, Berkeley Institute for Data Science. Berkeley, CA, USA.
February 27, 2018.
The Subtour LP for the Traveling Salesman Problem
Google. Mountain View, CA, USA.
January 24, 2018.
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 (Associate Professor, William and Mary Math)
- Chandrashekhar Nagarajan, August 2008 (Facebook)
- Yogeshwer Sharma, August 2010 (Facebook)
- Jiawei Qian, January 2012 (JW Capital)
- James Davis, August 2015 (Uber)
- Sin-Shuen Cheung, January 2016 (Google)
- Alice Paul, August 2017 (Postdoc, Brown University)
His current Ph.D. students are:
His former postdocs are:
- Matthias Poloczek (Assistant Professor, University of Arizona Systems and Industrial Engineering)