David P. Williamson
Professor and Chair of Information Science
Operations Research and Information Engineering
Biography
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.
Research Interests
Professor Williamson works in the area of discrete optimization. In particular, he designs efficient heuristics with provable performance guarantees for NP-hard optimization problems; these heuristics are known as approximation algorithms. He has worked on approximation algorithms for a broad range of problems of interest in the operations research community, including network design, scheduling, facility location, clustering, ranking, and other related problems. Currently he is focusing his research efforts on the traveling salesman problem and on simple approximation algorithms.
- Theory of Computation
- Complex Systems, Network Science and Computation
- Algorithms
- Information Technology Modeling
- Networks
- Optimization
Teaching Interests
Most recently, Williamson has taught ORIE 6334, a graduate-level course on spectral graph theory and algorithms, and ORIE 3310, a second semester optimization course for juniors.
Service Interests
Williamson is the former Editor-in-Chief for the SIAM Journal on Discrete Mathematics.
Selected Publications
- Williamson, David P., David Shmoys. 2011. The Design of Approximation Algorithms. : Cambridge University Press. New York, NY, United States: Cambridge University Press.
- Davis, James M., Huseyin Topaloglu, David P Williamson. 2017. “Pricing Problems Under the Nested Logit Model with a Quality Consistency Constraint.” INFORMS Journal on Computing 29 (1): 54-76.
- Couëtoux, Basile, James M. Davis, David P Williamson. 2015. “A 3/2-approximation algorithm for some minimum-cost graph problems.” Mathematical Programming 150 (1): 19-34.
- Schalekamp, Frans, David P. Williamson, Anke van Zuylen. 2014. “2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture.” Mathematics of Operations Research 39 (2): 403-417.
- Lin, Guolong, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P Williamson. 2010. “A General Approach for Incremental Approximation and Hierarchical Clustering.” SIAM Journal on Computing 39: 3633-3669.
Selected Awards and Honors
- SIAM Fellow (Society for Industrial and Applied Mathematics) 2016
- ACM Fellow (Association for Computing Machinery) (ACM) 2013
- Lanchester Prize for best contribution to operations research and the management sciences published in English (INFORMS) 2013
- College of Engineering Teaching Excellence Award (Cornell University) 2016
- Professor of the Year (ORIE Undergraduate Voted) (ORIE) 2016
Education
- B.S. (Mathematics), Massachusetts Institute of Technology, 1989
- M.S. (Computer & Information Science), Massachusetts Institute of Technology, 1990
- Ph.D. (Computer & Information Science), Massachusetts Institute of Technology, 1993