Scaling Methods for Discrete and Continuous Optimization

This project is funded by a European Research Council Starting Grant.

Open Positions

There are no openings at this time, but you can email me to register your future interest.

Project summary

The project focuses on problems and methods on the interface between discrete and continuous optimization. A key goal is to further our understanding of strongly polynomial computability, and make progress towards the important open question of finding a strongly polynomial algorithm for linear programming.

From the discrete optimization side, our goal is to extend strongly polynomial computability to LPs beyond integer constraint matrices. We will target problems such as generalized flows and Markov decision processes. Scaling is a classical method to obtain weakly and strongly polynomial algorithms for discrete optimization problems. We will use novel variants such as in our recent work on generalized flows.

From the continuous side, we will further develop the theory of geometric rescaling algorithms. This approach such combines first-order methods with geometric rescaling techniques to obtain a new family of polynomial-time algorithms. See this paper for such algorithms and for further references. We will also explore applications of this paradigm to combinatorial problems, such as submodular function minimization.