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–December 2022.

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


Team Members


Open Position

There are no openings at the moment.

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

Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husić, László A. Végh
STOC 2021
Directed Shortest Paths via Approximate Cost Balancing
James B. Orlin, László A. Végh
SODA 2021
Oriented Matroids from Triangulations of Products of Simplices
Marcel Celaya, Georg Loho, Chi Ho Yuen
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
Jugal Garg, Edin Husić, László A. Végh
STACS 2021
A Strongly Polynomial Label-Correcting Algorithm for Linear Systems with Two Variables per Inequality
Zhuan Khye Koh, Bento Natura, László A. Végh
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
Daniel Dadush, Bento Natura, László A. Végh
FOCS 2020
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
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.
Signed tropical convexity
Georg Loho, László A. Végh
ITCS 2020
Tropical Carathéodory with Matroids
Georg Loho, Raman Sanyal
Face posets of tropical polyhedra and monomial ideals
Georg Loho, Ben Smith
Tropical Ehrhart Theory and Tropical Volume
Georg Loho, Matthias Schymura
Research in the Mathematical Sciences, 7(30) (2020)
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg, László A. Végh
STOC 2019
Rescaling Algorithms for Linear Conic Feasibility
Daniel Dadush, László A. Végh, Giacomo Zambelli
Mathematics of Operations Research, 45(2):403–795, 2020.