A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg, László A. Végh
Accepted to STOC 2019

We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. The main measure of progress is identifying a set of edges that must correspond to best bang-per-buck ratios in every equilibrium, called the revealed edge set. We use a variant of the combinatorial algorithm by Duan and Mehlhorn to identify a new revealed edge in a strongly polynomial number of iterations. Every time a new edge is found, we use a subroutine to identify an approximately best possible solution corresponding to the current revealed edge set. Finding the best solution can be reduced to solving a linear program. Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time.

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, László A. Végh
STOC 2018, Best Paper Award
Talk at Simons Institute
Two hour board talk at the Hausdorff institute: Part I, Part II
Article in Quanta Magazine

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.

Decomposable Submodular Function Minimization: Discrete and Continuous
Alina Ene, Huy L. Nguyen, László A. Végh
NIPS 2017

This paper investigates connections between discrete and continuous approaches for decomposable submodular function minimization. We provide improved running time estimates for the state-of-the-art continuous algorithms for the problem using combinatorial arguments. We also provide a systematic experimental comparison of the two types of methods, based on a clear distinction between level-0 and level-1 algorithms.

Geometric Rescaling Algorithms for Submodular Function Minimization
Daniel Dadush, László A. Végh, Giacomo Zambelli
SODA 2018.

We present a new class of polynomial-time algorithms for submodular function minimization (SFM), as well as a unified framework to obtain strongly polynomial SFM algorithms.

A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
Neil Olver, László A. Végh
STOC 2017

We present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given in [Végh16]; our new algorithm is much simpler, and much faster. The complexity bound O((m+n log n)mnlog(n2/m)) improves on the previous estimate in [Végh16] by almost a factor O(n2). Even for small numerical parameter values, our algorithm is essentially as fast as the best weakly polynomial algorithms. The key new technical idea is relaxing primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.