# 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

• László Végh Principal Investigator
• Yixin Tao Postdoctoral Researcher, October 2020–
• Georg Loho Postdoctoral Researcher, February 2019–September 2020&
• Zhuan Khye (Cedric) Koh 3rd Year PhD Student
• Bento Natura 3rd Year PhD Student
• Edin Husić 4th Year PhD Student, partially supported by the ERC grant
• Farbod Ekbatani
Part-Time Research Assistant, December 2020–
• Patrick Veenstra
Part-Time Research Assistant, January–April 2019

### 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 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