2024 Tucker Prize Citation

The A. W. Tucker Prize 2024 is presented to Yang Liu for the thesis Sparsification, Online Optimization, and an Almost-Linear Time Algorithm for Maximum Flow.

This thesis is a tour de force that tackles multiple fundamental optimization questions from unique and modern angles. First, Liu gives an almost-linear-time algorithm that computes exact maximum- and minimum-cost flows in directed graphs. Second, he offers methods with nearly optimal complexity properties for solving lp-norm regression problems, leveraging new sparsification techniques. Finally, Liu considers online discrepancy minimization: given a sequence of T n-dimensional vectors with norm x ≤ 1, the linear-time algorithm succeeds with high probability to choose signs such that the signed sum of vectors is below O(log nT).

The other two Tucker Prize finalists chosen by this year's Tucker Prize Committee are Jason Altschuler and Nathan Klein.

Nathan Klein's thesis Finding Structure in Entropy: Improved Approximation Algorithms for TSP and other Graph Problems revisits a fundamental question in the design of approximation algorithms for solving the traveling salesman problem (TSP). In particular, it revisits the decades-old question of whether it is possible to improve upon the (3/2)-approximation algorithm of Christofides & Serdyukov for metric TSP. Incredibly, after considerable effort by many to answer this question, this thesis proves that for at least some small epsilon there exists a deterministic ((3/2)- epsilon)-approximation algorithm for metric TSP, and that the integrality gap of the natural LP relaxation for TSP is at most (3/2)-epsilon. The Christofides and Serdyukov algorithm yields no better than a (3/2)-approximation because it can be saddled with a spanning tree (for initialization) with poor properties. Klein's thesis (1) leverages a “max entropy” approach for choosing a random initial spanning tree based on a carefully chosen distribution and proves that this yields undesirable properties with low probability; and (2) proves new properties about the structure of near-minimum cuts of graphs, which in turn gives a setting in which the prior probabilistic tools can be applied.

Jason Altschuler's dissertation Transport and Beyond: Efficient Optimization Over Probability Distributions studies two optimization problems for which the decision variables are probability distributions. Both parts relate to optimal transport, a geometrically meaningful measure of distance between any pair of probability distributions that has received substantial attention in areas such as machine learning. The first part focuses on optimal transport with so-called entropic regularization. Altschuler's thesis shows that the seemingly distinct problems of optimal transport, min-meancycle, matrix balancing, and matrix scaling can all be viewed under the same lens as optimization over a joint probability distribution with similarly constrained marginals. Using this lens, the thesis provides approximation algorithms for all four problems that have nearly optimal run times, namely, close to the n² run time required merely to read an n-by-n matrix input. The second part of the thesis goes beyond the setting of optimization over joint probability distributions with two marginals to multimarginal optimal transport (MOT) problems with k ≥ 2 marginals. Such problems, which arise in data science, PDE simulation, and quantum chemistry, are difficult in fundamental ways. The thesis addresses multiple questions about the potential polynomial-time solvability of MOT problems. It shows that certain MOT problems are indeed intractable, while also offering a unified algorithmic framework—built upon classical ideas from oracle-based optimization algorithms— for solving certain structured MOT problems.