ScaleOptScaling Methods for Discrete and Continuous OptimizationThis 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 

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
PartTime Research Assistant, December 2020–  Patrick Veenstra
PartTime 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 minimumcost 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 layeredleastsquares interiorpoint 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 firstorder methods with geometric rescaling techniques to obtain a new family of polynomialtime 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 ArrowDebreu 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 LabelCorrecting 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 scalinginvariant 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 