David P. Williamson is the Director of the School of Operations Research and Information Engineering at Cornell University. He is also a Professor in 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.
PhD in Computer Science, 1993
MIT
SM in Computer Science, 1990
MIT
SB in Mathematics, 1989
MIT
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
To appear in Mathematical Programming B.
DOI
Graph Coloring and Semidefinite Rank
Mathematical Programming B 206:577-605, 2024.
DOI
A Lower Bound on the Max Entropy Algorithm for TSP
In Jens Vygen and Jaroslaw Byrka, editors, Lecture Notes in Computer Science volume 14679, Integer Programming and Combinatorial Optimization (IPCO 2023), pages 238–251, 2025.
Preprint
DOI
Max Cut and Semidefinite Rank
Operations Research Letters 53, Article 107067, 2024.
DOI
Erratum to 'Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems'
Mathematics of Operations Research 48:2304-2307, 2023
DOI