David P. Williamson is the Chair of the Department of Information Science at Cornell University, and a Professor 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.
PhD in Computer Science, 1993
MIT
SM in Computer Science, 1990
MIT
SB in Mathematics, 1989
MIT
Tight Bounds for Online Weighted Tree Augmentation
To appear in Algorithmica.
Preprint
DOI
Improved Analysis of RANKING for Online Vertex-Weighted Matching
To appear in WINE 2021.
Preprint
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
To appear, Mathematics of Operations Research
Preprint
DOI
Recursive Random Contraction Revisited
In the Proceedings of the 2021 SIAM Symposium on Simplicity in Algorithms, pages 68-73, 2021.
Preprint
DOI
Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time
In the Proceedings of the 19th IEEE International Conference on Machine Learning and Applications, pages 19-24, 2020.
Preprint
DOI