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 ChvatalGomory 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 Mellipsoid of a convex body, and a muchimproved
and nearlyoptimal 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 semialgebraic geometry and nonsmooth
optimization theory and applying these to semialgebraic or socalled 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 postdoctoral
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, minmax results for the
2terminal case, and a primaldual 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 branchandcut algorithm, enabled her to obtain solutions for
the realworld 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.
