Scaling Methods for Discrete and Continuous OptimizationThis project is funded by a European Research Council Starting Grant.
Open PositionsMultiple postdoc and PhD student positions will be available. Please email me if you are interested.
Applicants for PhD positions should be submitted via the LSE PhD application system. Please visit the departmental PhD application website for application guidance. Early application is encouraged. Please contact me before submitting your application.
Project summaryThe 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.