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 current job advertisment for a postdoc position (officially called "research officer") is available here. The length of the position is 1 year with possible extensions; the starting date is flexible. The closing date for applications is 8 December 2017 (23.59 UK time).

Applicants for PhD positions should be submitted via the LSE PhD application system. Please visit the departmental PhD application website for application guidance. The application deadline for positions in this project is 28 February 2018, but late applications may also be considered. Please contact me before submitting your application.

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.