معرفی
David P. Williamson is a Professor at Cornell University in the School of Operations Research and Information Engineering (ORIE), with a significant leadership role as former Chair of the Department of Information Science in the Cornell Ann S. Bowers College of Computing and Information Science from July 2021 through December 2023. His academic journey began at MIT where he earned his B.S. in Mathematics (1989), followed by an M.S. (1990) and Ph.D. (1993) in Computer & Information Science under Professor Michel X. Goemans. After completing a postdoc at Cornell under Professor Éva Tardos, he worked at IBM Research at both the T.J. Watson Research Center and Almaden Research Center before joining Cornell University in 2004.
- 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)
Professor Williamson's research centers on discrete optimization, specializing in approximation algorithms for NP-hard optimization problems. His work spans network design, scheduling, facility location, clustering, ranking, and particularly the traveling salesman problem. He has made seminal contributions to the field, evidenced by his co-authored paper 'Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming' which earned the 2022 AMS Steele Prize. His research approach emphasizes simple yet powerful approximation algorithms with provable performance guarantees, bridging theoretical computer science and operations research.
Analysis of his recent publications reveals a strong focus on the traveling salesman problem, with particular attention to integrality gaps of semidefinite programming relaxations, combinatorial algorithms for solving Laplacian systems, and novel approaches to cycle cut instances. His work consistently demonstrates how theoretical insights can yield practical algorithmic improvements, with applications spanning network design, revenue management, and graph theory. Williamson has also contributed significantly to educational resources through his textbook 'Network Flow Algorithms' (2019) and 'The Design of Approximation Algorithms' (2011, with David Shmoys).
- American Mathematical Society Steele Prize for Seminal Contribution to Research (2022)
- SIAM Fellow (2016)
- ACM Fellow (2013)
- Lanchester Prize for best contribution to operations research (2013)
- Professor of the Year (ORIE Undergraduate Voted) (2018)
- ACM STOC 30-year Test of Time Award (2024)
Professor Williamson has demonstrated significant academic leadership through his service as Chair of the Department of Information Science and as former Editor-in-Chief for the SIAM Journal on Discrete Mathematics. His teaching portfolio includes undergraduate courses like ENGRI 1101 (introduction to operations research) and ORIE 1380 (introduction to data science), as well as graduate courses including ORIE 6330 (network flows) and ORIE 6334 (spectral graph theory and algorithms). His research has attracted substantial funding from the National Science Foundation, including awards for projects like 'AF: Small: Looking Under Rocks: A Search for a Provably Stronger TSP Relaxation' (2019) and 'AF: EAGER: Approximation algorithms for the traveling salesman problem' (2015).
While specific laboratory affiliations aren't detailed in the available information, Professor Williamson's work is deeply embedded in Cornell's theoretical computer science and operations research communities. His research collaborations span multiple institutions, with frequent co-authorship with colleagues at Cornell and beyond. His recent publications indicate active engagement with current challenges in approximation algorithms, particularly those related to the traveling salesman problem and semidefinite programming relaxations, suggesting ongoing leadership in these critical areas of theoretical computer science and operations research.
