Scaling Methods for Discrete and Continuous Optimization

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

Open Positions

There is currently an opening for a research officer (post doc) position with application due date 14 November 2018. Please see the official advertisement here.

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.

Project members