Scaling Methods for Discrete and Continuous Optimization

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

Open Positions

Multiple postdoc and PhD student positions are available. Please email me if you are interested. The official job advertisements will be posted later.

Project summary

The project focuses on problems and methods on the interface between discrete and continuous optimization. An important 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. We will use novel combinatorial scaling techniques, 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.