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

László Végh Principal Investigator
Sharat Ibrahimpur Postdoctoral Researcher, September 2022–
Christoph Hertrich Postdoctoral Researcher, January 2022–
Yixin Tao Postdoctoral Researcher, October 2020–January 2023
Georg Loho Postdoctoral Researcher, February 2019–September 2020
Currently Assistant Professor at the University of Twente
Zhuan Khye (Cedric) Koh PhD student, September 2018–September 2022, currently postdoc at CWI.
Bento Natura PhD student, September 2018– July 2022, currently postdoc at Georgia Tech.
Edin Husić PhD student, September 2017–September 2021. Partially supported by the ERC grant. Currently postdoc at IDSIA Lugano.
Farbod Ekbatani Part-Time Research Assistant, December 2020–June 2021. Currently PhD student at the University of Chicago.
Patrick Veenstra
Part-Time Research Assistant, January–April 2019

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	JACM version STOC version arXiv:1611.01778
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