The committee has decided to give two awards this year.
Winners
- Ernest K. Ryu (Department of Mathematics, University of California, Los Angeles, USA)
for the paper entitled “Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting.” Mathematical Programming 182 (1): 233-273, 2020.
Citation
Douglas-Rachford splitting (DRS) is a very influential operator splitting method, which was first used in numerical PDE in 1956 and later formalized by Lions and Mercier in 1979 to solve the maximal monotone inclusion problems. Two pivotal questions had remained open for forty years regarding DRS: (i) Is DRS the only choice for maximal monotone inclusion problems involving two operators? (ii) Can we extend DRS to maximal monotone inclusion problems involving three operators? The cited paper successfully addressed these two open questions by highly innovative techniques. First, it rigorously defined the notion of “admissible conditions”, which includes “frugality” and “no lifting”. Second, it proved that (i) DRS is the only admissible operator for maximal monotone inclusion problem with two operators, and (ii) there is no admissible operator for maximal monotone inclusion problem with three operators. Moreover, the cited paper proposed a new operator splitting algorithm with exciting perspectives for problems involving arbitrary number of operators. In summary, results in the cited paper resolved longstanding open questions in the field, and the highly skillful techniques in the proof as well as the notions of “frugality” and “no lifting” have generated a series of exciting follow-up work by other researchers.
- Joseph Paat, (Sauder School of Business, University of British Columbia, Canada)
Ingo Stallknecht, (Isha Foundation, India)
Zach Walsh, (Department of Mathematics and Statistics, Auburn University, USA)
Luze Xu (Department of Mathematics, University of California, Davis, USA)
for their joint paper “On the column number and forbidden submatrices for $\Delta$-modular matrices.” SIAM J. Discrete Mathematics, Vol 38, No 1, pp. 1-18, 2024.
Citation
A major open question in integer programming that has attracted a lot of interest recently is whether integer programs defined over $\Delta$-modular matrices can be solved in polynomial time, assuming $\Delta$ is fixed. A matrix is $\Delta$-modular if every full-rank square submatrix has the absolute value of its determinant bounded above by a positive integer $\Delta$. It was known for a long time that this question has an affirmative answer when $\Delta= 1$, and more recently a polynomial time algorithm was obtained for $\Delta = 2$. The question remains open for $\Delta \geq 3$. As any answer to this question implicitly builds upon difficult results such as Seymour's characterization of totally unimodular matrices, and needs to combine results from matroid theory and polyhedral combinatorics, it is expected that this question is a difficult one to answer. Paat et. al. provide elegant new results that advance the study of $\Delta$-modular matrices while using techniques from multiple areas of discrete optimization. They not only improve upon earlier results and give a tight bound on the number of possible columns a $\Delta$-modular matrix can have, they also give families of matrices that form forbidden substructures in $\Delta$-modular matrices. We believe that their results will shed new light on the above-mentioned open question.
Prize committee
Merve Bodur, Sanjeeb Dash, Shiqian Ma, Andy Sun (chair)