ScaleOpt

Scaling Methods for Discrete and Continuous Optimization

This project is funded by a Starting Grant from the European Research Council, under the European Union's Horizon 2020 research and innovation programme, grant agreement no. 757481.

Duration: January 2018–June 2023.

Hosted by: Department of Mathematics
London School of Economics and Political Science


Team Members


Open Position

We have an opening for a postdoc position in Algorithms and Optimisation, jointly with Neil Olver. Please see the advertisement here. The application deadline is 13 May 2022 (23.59 UK time).

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 (LP). Some main streams of research are the following.

From the discrete optimization side, our goal is to extend strongly polynomial computability to broader classes of linear programs. One particularly relevant class of LP is when each column of the constraint matrix has at most two nonzero entries; this is equivalent to the minimum-cost generalized flow problem. Novel variants of the classical scaling methods lead to the first strongly polynomial algorithm for the maximum generalized flow problem. Another interesting class of LPs correspond to undiscounted Markov Decision Processes.

Our recent work has revisited classical results on linear programming. We developed a a new layered-least-squares interior-point method with significantly improved running times that is strongly polynomial for a broad class of problem instances. In a second paper we showed how the latest improvements in the complexity of approximate solvers translate to fast strongly polynomial algorithms.

Another line of work addresses geometric rescaling algorithms. This approach 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.

Strongly polynomial solvability of LP is inherently connected to the polynomial time solvability of mean payoff games, or equivalently, tropical linear programs, a famous problem in NP$\cap$coNP. See this paper by Allamigeon et al. for a particularly nice connection. Our goal is to further explore the relationship between these problems. Our recent paper develops a new convexity notion for signed tropical numbers.

Market equilibrium models provide some particularly interesting examples of convex programs that are strongly polynomially solvable. We have established the strongly polynomial computability of an equilibrium in linear Arrow-Debreu markets in this paper.

In the related area of fair division, we obtained the first constant factor approximation for Nash social welfare for a broad class of gross substitute utility functions.

Research Visitors

2019

Jugal Garg (March), Dani Dorfman (March), Sophie Huiberts (July), Michail Fasoulakis (Nov).

2018

Tamás Király (Feb), Jugal Garg (March), Sergei Chubanov (March), Jefferson Huang (March/April), Fabrizio Grandoni (April), Georg Loho (April), Daniel Dadush (Sep), Kristóf Bérczi (Oct), Vera Traub (Dec).

Publications and Manuscripts

(To be updated)
Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husić, László A. Végh
STOC 2021 		arXiv:2009.14793
Directed Shortest Paths via Approximate Cost Balancing
James B. Orlin, László A. Végh
SODA 2021 		SODA version
arXiv:2007.07975
Oriented Matroids from Triangulations of Products of Simplices
Marcel Celaya, Georg Loho, Chi Ho Yuen
arXiv:2005.01787
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
Jugal Garg, Edin Husić, László A. Végh
STACS 2021 		arXiv:1908:07948
A Strongly Polynomial Label-Correcting Algorithm for Linear Systems with Two Variables per Inequality
Zhuan Khye Koh, Bento Natura, László A. Végh
arXiv:2004.08634
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
Daniel Dadush, Bento Natura, László A. Végh
FOCS 2020
arXiv:2009.04942
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Daniel Dadush, Sophie Huiberts, Bento Natura, László A. Végh
STOC 2020 		STOC version
arXiv:1912.06252
A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
Neil Olver, László A. Végh
Journal of the ACM, 67(2):10, 2020.
Conference version: STOC 2017
Geometric Rescaling Algorithms for Submodular Function Minimization
Daniel Dadush, László A. Végh, Giacomo Zambelli
Accepted to Mathematics of Operations Research, 2020.
Conference version: SODA 2018. 		SODA version
arXiv:1707.05065
Signed tropical convexity
Georg Loho, László A. Végh
ITCS 2020 		ITCS version
arXiv:1906:06686
Tropical Carathéodory with Matroids
Georg Loho, Raman Sanyal
arXiv:1912.11262
Face posets of tropical polyhedra and monomial ideals
Georg Loho, Ben Smith
arXiv:1909:01236
Tropical Ehrhart Theory and Tropical Volume
Georg Loho, Matthias Schymura
Research in the Mathematical Sciences, 7(30) (2020)
arXiv:1908.07893
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg, László A. Végh
STOC 2019 		STOC version
arXiv:1809.06266
Rescaling Algorithms for Linear Conic Feasibility
Daniel Dadush, László A. Végh, Giacomo Zambelli
Mathematics of Operations Research, 45(2):403–795, 2020. 		arXiv:1611.06427