Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, Jan Vondrák
Accepted to STOC 2023

For any $\varepsilon>0$, we give a simple, deterministic $(6+\varepsilon)$-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents' valuations, and give an $(\omega + 2 + \varepsilon) e$-approximation if the ratio between the largest weight and the average weight is at most $\omega$.
We also show that the $1/2$-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time which is both $1/2$-EFX and a $(12+\varepsilon)$-approximation to the symmetric NSW problem under submodular valuations. The previous best approximation factor under $1/2$-EFX was linear in the number of agents.

An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem
Satoru Fujishige, Tomonari Kitahara, László A. Végh
Accepted to IPCO 2023

We consider the minimum-norm-point (MNP) problem over zonotopes, a well-studied problem that encompasses linear programming. Inspired by Wolfe's classical MNP algorithm, we present a general algorithmic framework that performs first order update steps, combined with iterations that aim to `stabilize' the current iterate with additional projections, i.e., finding a locally optimal solution whilst keeping the current tight inequalities. We bound on the number of iterations polynomially in the dimension and in the associated circuit imbalance measure. In particular, the algorithm is strongly polynomial for network flow instances. The conic version of Wolfe's algorithm is a special instantiation of our framework; as a consequence, we obtain convergence bounds for this algorithm. Our preliminary computational experiments show a significant improvement over standard first-order methods.

On the Correlation Gap of Matroids
Edin Husić, Zhuan Khye Koh, Georg Loho, László A. Végh
Accepted to IPCO 2023

The correlation gap of a set function measures the ratio between two natural extensions. It has has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is $1-1/e$, and this is tight even for simple matroid rank functions.
We initiate a fine-grained study of correlation gaps of matroid rank functions. In particular, we present improved lower bounds on the correlation gap as parametrized by the rank and the girth of the matroid. We also show that the worst correlation gap of a weighted matroid rank function is achieved under uniform weights.

Interior point methods are not worse than Simplex
Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura, László A. Végh
FOCS 2022

We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound $O(2^nn^{1.5}\log n)$ for an $n$-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most $O(n^{1.5}\log n)$ times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the `max central path', a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths.

On Circuit Diameter Bounds via Circuit Imbalances
Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh
IPCO 2022

We study the circuit diameter of polyhedra, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA, 2015) as a relaxation of the combinatorial diameter. We show that the circuit diameter of a system $\{x\in \mathbb{R}^n:\, Ax=b, 0\le x\le u\}$ for $A\in\mathbb{R}^{m\times n}$ is bounded as $O(m^2\log(m+\kappa_A)+n\log n)$, where $\kappa_A$ is the circuit imbalance measure of the constraint matrix. This yields a strongly polynomial circuit diameter bound e.g. if all entries of A have polynomially bounded encoding length in n. Further, we present circuit augmentation algorithms for LPs using the minimum-ratio circuit cancelling rule. Even though the standard minimum-ratio circuit cancelling algorithm is not finite in general, our variant can solve an optimization LP in $O(n^3\log(n+\kappa_A))$ augmentation steps.

On finding exact solutions of linear programs in the oracle model
Daniel Dadush, Giacomo Zambelli, László A. Végh
SODA 2022

On complete classes of valuated matroids
Edin Husić, Georg Loho, Ben Smith, László A. Végh
SODA 2022

We characterize a rich class of valuated matroids, called R-minor valuated matroids that includes the indicator functions of matroids, and is closed under operations such as taking minors, duality, and induction by network. We refute the refinement of a 2003 conjecture by Frank, exhibiting valuated matroids that are not R-minor. The family of counterexamples is based on sparse paving matroids. Valuated matroids are inherently related to gross substitute valuations in mathematical economics. By the same token we refute the Matroid Based Valuation Conjecture by Ostrovsky and Paes Leme (Theoretical Economics 2015) asserting that every gross substitute valuation arises from weighted matroid rank functions by repeated applications of merge and endowment operations. Our result also has implications in the context of Lorentzian polynomials: it reveals the limitations of known construction operations.

Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets
Jugal Garg, Yixin Tao, László A. Végh
SODA 2022

We study the equilibrium computation problem in the Fisher market model with constrained piecewise linear concave (PLC) utilities. This general class captures many well-studied special cases, including markets with PLC utilities, markets with satiation, and matching markets. For the special case of PLC utilities, although the problem is PPAD-hard, Devanur and Kannan (FOCS 2008) gave a polynomial-time algorithm when the number of items is constant. Our main result is a fixed parameter approximation scheme for computing an approximate equilibrium, where the parameters are the number of agents and the approximation accuracy. This provides an answer to an open question by Devanur and Kannan for PLC utilities, and gives a simpler and faster algorithm for matching markets as the one by Alaei, Jalaly and Tardos (EC 2017). The main technical idea is to work with the stronger concept of thrifty equilibria, and approximating the input utility functions by `robust' utilities that have favorable marginal properties. With some restrictions, the results also extend to the Arrow--Debreu exchange market model.

Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husić, László A. Végh
STOC 2021

We present the first constant-factor approximation algorithm for the symmetric Nash social welfare problem under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.

Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
Jugal Garg, Edin Husić, László A. Végh
STACS 2021

We present a simple auction algorithm that obtains an approximate market equilibrium for the exchange market model with divisible goods where the demands of the agents satisfy the weak gross substitutes (WGS) property. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash Social Welfare problem.

Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
Daniel Dadush, Bento Natura, László A. Végh
FOCS 2020

Tardos (Oper. Res. '86) showed that solving an LP $\min \langle c, x \rangle$, $Ax=b$, $x \geq 0$, $A \in \Z^{m \times n}$, can be reduced to solving $O(mn)$ LPs in $A$ having small integer coefficient objectives and right-hand sides using any exact LP algorithm. In this work, we give a substantially improved framework, in which we remove the integrality requirement of $A$, using a dependence on the condition measure $\bar{\chi}_A$. We also replace the exact LP solves with approximate ones, enabling us to directly leverage the tremendous recent algorithmic progress for approximate linear programming.

Signed tropical convexity
Georg Loho, László A. Végh
ITCS 2020

We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.