2015 Tucker Prize Citation

The Tucker Prize for an outstanding doctoral thesis has been awarded to Daniel Dadush for his thesis `Integer Programming, Lattice Algorithms, and Deterministic Volume Computation written at Georgia Tech.

Daniel Dadush obtained an ScB in Mathematics from Brown University in 2006, and a PhD from the Algorithms, Combinatorics, and Optimization program at Georgia Tech under the guidance of Santosh Vempala in 2012. He is currently a tenure track researcher at Centrum Wiskunde and Informatica in Amsterdam.

In his PhD thesis "Integer Programming, Lattice Algorithms, and Deterministic Volume Computation" Dadush presents several impressive results on algorithmic convex geometry, geometry of lattices, and the complexity of integer programming. His results include a proof of the claim that the Chvatal-Gomory closure of a convex body is a rational polyhedron, improved algorithms for finding the shortest and closest lattice vectors, an optimal deterministic algorithm for computing an M-ellipsoid of a convex body, and a much-improved and nearly-optimal deterministic algorithm for computing the volume of a convex body. By combining all the techniques derived in his thesis, Dadush derives the fastest currently known algorithm for integer programming. The complexity of the algorithm represents a significant improvement over classical algorithms by Lenstra and by Kannan and shows Dadush's deep understanding of lattice techniques and convex geometry. In his work Dadush pays great attention to detail and exposition, which results in a thesis that is truly worthy of the 2015 A.W. Tucker prize.

The other two Tucker Prize finalists chosen by this year's Tucker Prize Committee are Dmitriy Drusvyatskiy and Marika Karbstein.

Dmitriy Drusvyatskiy received a BS degree in Computer Science in 2008 from New York University Polytechnic Institute and a PhD degree from the School of Operations Research and Information Engineering at Cornell University in 2013. He is currently an Assistant Professor in the Department of Mathematics at University of Washington.

His PhD thesis "Slope and Geometry in Variational Mathematics" was supervised by Adrian S. Lewis and distinguishes itself by its scope, developing fundamental concepts in mathematical optimization through a unique blend of semi-algebraic geometry and nonsmooth optimization theory and applying these to semi-algebraic or so-called tame optimization problems. It gives the mildest of conditions for many striking results in tame optimization, such as convergence of the alternating projection method, finite length of nearly steepest descent paths, and finite cardinality of Clarke critical points. A crucial contribution of this thesis is the concept of a "minimal identifiable set" for nonsmooth optimization which is independent of the functional representation of the problem and provides a unifying tool for studying optimality conditions, sensitivity, and the design of active set algorithms. In summary, built on rich imagination and creativity, this dissertation makes an inspiring set of fundamental and far reaching conclusions in the area of nonsmooth optimization.

Marika Karbstein obtained a Diploma in Mathematics with Economics from Technische Universitaet Berlin in 2005. In 2013, she completed a PhD in Mathematics at the same university under the supervision of Ralf Borndoerfer and Martin Groetschel. She is currently a post-doctoral research fellow at the Zuse Institute Berlin.

The thesis of Karbstein, titled "Line Planning and Connectivity", consists of a variety of contributions to line planning for public transportation. She introduced the Steiner connectivity problem as a prototypical model for line planning and extended known results for the Steiner tree problem such as polyhedral results, min-max results for the 2-terminal case, and a primal-dual approximation algorithm to this new framework.

To solve the integrated problem for line planning and passenger routing, she introduced a new model with a transfer penalty. This approach, together with the design of cutting planes and the implementation of a branch-and-cut algorithm, enabled her to obtain solutions for the real-world instance that arises in the public transportation system in Potsdam. Her solution was adopted after a minor modification and worked smoothly in practice. This is definitely a milestone success in mathematical approaches to traffic optimization.