About

David Williamson is a professor in the Department of Computer Science at Cornell University. His research interests include areas such as AI ethics and policy, algorithmic fairness and discrimination, natural language processing, and human-AI interaction. The page does not provide detailed information about his background, specific research contributions, or academic history.

Research topics

• Computer Science
• Mathematics
• Mathematical optimization
• Theoretical computer science
• Algorithm
• Economics
• Programming language
• Finance
• Statistics

Selected publications

• The two-stripe symmetric circulant TSP is in P

  Mathematical Programming · 2025-04-17 · 1 citations

  articleSenior author
  PublisherDOI

• A $$\frac{4}{3}$$-approximation algorithm for half-integral cycle cut instances of the TSP

  Mathematical Programming · 2025-02-17

  articleSenior author
  PublisherDOI

• Graph coloring and semidefinite rank

  Mathematical Programming · 2024-04-24

  articleSenior author
  PublisherDOI

• Max cut and semidefinite rank

  Operations Research Letters · 2024-01-21

  articleSenior author
  PublisherDOI

• A Lower Bound for the Max Entropy Algorithm for TSP

  Lecture notes in computer science · 2024-01-01

  book-chapterSenior author
  PublisherDOI

• A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP

  Lecture notes in computer science · 2023-01-01 · 2 citations

  book-chapterSenior author
  PublisherDOI

• A Lower Bound for the Max Entropy Algorithm for TSP

  arXiv (Cornell University) · 2023-11-03

  preprintOpen accessSenior author

  One of the most famous conjectures in combinatorial optimization is the four-thirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to $\frac43$. For 40 years, the best known upper bound was 1.5, due to Wolsey (1980). Recently, Karlin, Klein, and Oveis Gharan (2022) showed that the max entropy algorithm for the TSP gives an improved bound of $1.5 - 10^{-36}$. In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graphic TSP. Thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the four-thirds conjecture in the affirmative, should that be possible.

  PublisherOA PDFDOI

• Revisiting Garg's 2-Approximation Algorithm for the <i>k</i>-MST Problem in Graphs

  Society for Industrial and Applied Mathematics eBooks · 2023-01-01

  book-chapterOpen accessSenior author

  This paper revisits the 2-approximation algorithm for k-MST presented by Garg [9] in light of a recent paper of Paul et al. [14]. In the k-MST problem, the goal is to return a tree spanning k vertices of minimum total edge cost. Paul et al. [14] extend Garg's primal-dual subroutine to improve the approximation ratios for the budgeted prize-collecting traveling salesman and minimum spanning tree problems. We follow their algorithm and analysis to provide a cleaner version of Garg's result. Additionally, we introduce the novel concept of a kernel which allows an easier visualization of the stages of the algorithm and a clearer understanding of the pruning phase. Other notable updates include presenting a linear programming formulation of the k-MST problem, including pseudocode, replacing the coloring scheme used by Garg with the simpler concept of neutral sets, and providing an explicit potential function.

  PublisherOA PDFDOI

• GILP: An Interactive Tool for Visualizing the Simplex Algorithm

  2023-03-02 · 6 citations

  preprintSenior author

  The Simplex algorithm for solving linear programs---one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century---is an important topic in many algorithms courses. While the algorithm relies on intuitive geometric ideas, the computationally-involved mechanics of the algorithm can obfuscate a geometric understanding. In this paper, we present gilp, an easy-to-use Simplex algorithm visualization tool designed to connect the mechanical steps of the algorithm with their geometric interpretation. We provide an extensive library of example visualizations, and our tool allows instructors to quickly produce custom interactive HTML files for students to experiment with the algorithm (without requiring students to install anything!). The tool can also be used for interactive assignments in Jupyter notebooks, and has been incorporated into a forthcoming Data Science and Decision Making interactive textbook. In this paper, we first describe how the tool fits into the existing algorithm visualization literature: how it was designed to facilitate student engagement and instructor adoption, and how it substantially extends existing algorithm visualization tools for Simplex. We then describe the development and usage of the tool, and report feedback from its use in a course with roughly 100 students. Student feedback was overwhelmingly positive, with students finding the tool easy to use: it effectively helped them link the algebraic and geometrical views of the Simplex algorithm and understand its nuances. Finally, gilp is open-source, includes an extension to visualizing linear programming-based branch and bound, and is readily amenable to further extensions.

  PublisherDOI

• Fluid Approximations for Revenue Management Under High-Variance Demand

  Management Science · 2023 · 18 citations

  Senior authorCorresponding
  • Computer Science
  • Computer Science
  • Mathematical optimization

  One of the most prevalent demand models in the revenue management literature is based on dividing the selling horizon into a number of time periods such that there is at most one customer arrival at each time period. This demand model is equivalent to using a discrete-time approximation to a Poisson process, but it has an important shortcoming. If the mean number of customer arrivals is large, then the coefficient of variation of the number of customer arrivals has to be small. In other words, large demand volume and large demand variability cannot coexist in this demand model. In this paper, we start with a revenue management model that incorporates general mean and variance for the number of customer arrivals. This revenue management model has a random selling horizon length, capturing the distribution of the number of customer arrivals. The question we seek to answer is the form of the fluid approximation that corresponds to this revenue management model. It is tempting to construct the fluid approximation by computing the expected consumption of the resource capacities in the constraints and the total expected revenue in the objective function through the distribution of the number of customer arrivals. We demonstrate that this answer is wrong in the sense that it yields a fluid approximation that is not asymptotically tight as the resource capacities get large. We give an alternative fluid approximation where perhaps surprisingly, the distribution of the number of customer arrivals does not play any role in the constraints. We show that this fluid approximation is asymptotically tight as the resource capacities get large. A numerical study also demonstrates that the policies driven by the latter fluid approximation perform substantially better, so there is practical value in getting the fluid approximation right under high-variance demand. This paper was accepted by Omar Besbes, revenue management and market analytics. Funding: The work of the O. El Housni and H. Topaloglu was supported by a seed grant from Urban Tech research hub at Cornell Tech. Supplemental Material: The data files and online appendix are available at https://doi.org/10.1287/mnsc.2023.4769 .

  PublisherDOI

Recent grants

• AF: EAGER: Approximation algorithms for the traveling salesman problem

  NSF · $100k · 2015–2017

• AF: SMALL: Topics in Bridging Continuous and Discrete Optimization

  NSF · $430k · 2020–2024

• AF: Small: The Traveling Salesman Problem and Lightweight Approximation Algorithms

  NSF · $350k · 2011–2016

• AF: Small: Looking Under Rocks: A Search for a Provably Stronger TSP Relaxation

  NSF · $106k · 2019–2021

• Resolving Anomalies in Approximation Algorithms

  NSF · $204k · 2005–2008

Frequent coauthors

• David B. Shmoys

  Cornell University

  66 shared

• Alice Paul

  Brown University

  29 shared

• Michel X. Goemans

  29 shared

• Aaron Ferber

  26 shared

• Daniel Freund

  Massachusetts Institute of Technology

  25 shared

• Anke van Zuylen

  Cornell University

  19 shared

• Samuel C. Gutekunst

  16 shared

• Billy Jin

  Cornell University

  14 shared

Education

• Ph.D.

  Massachusetts Institute of Technology

  1993

Awards & honors

• SIAM DiPrima Prize (1996)
• Tucker Prize from the Mathematical Programming Society (1994…
• SIAM Activity Group on Optimization prize (1999)
• Fulkerson Prize from the Mathematical Programming Society an…
• Society for Industrial and Applied Math (SIAM) Fellow (2016)