On complete classes of valuated matroids
Edin Husić, Georg Loho, Ben Smith, László A. Végh 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. |
arXiv:2107:06961 |
Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets
Jugal Garg, Yixin Tao, László A. Végh 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. |
arXiv:2107:05700 |
An Accelerated Newton-Dinkelbach Method and its Application to Two
Variables Per Inequality Systems
Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh Accepted to ESA 2021. We present an accelerated, or 'look-ahead' version of the Newton-Dinkelbach method. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain new strongly polynomial algorithms for various problems. In particular, we obtain an improved convergence bound for linear fractional combinatorial optimization, and a strongly polynomial label-correcting algorithm for solving linear feasibility systems with two variables per inequality (2VPI). |
arXiv:2004.08634 |
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. |
arXiv:2009.14793 |
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. |
STACS version
arXiv:1908:07948 |
Directed Shortest Paths via Approximate Cost Balancing
James B. Orlin, László A. Végh SODA 2021 We present an $O(nm)$ algorithm for all-pairs shortest paths computations in a directed graph with $n$ nodes, $m$ arcs, and nonnegative integer arc costs. This matches the complexity bound attained by Thorup (1999) for the all-pairs problems in undirected graphs. Our main insight is that shortest paths problems with approximately balanced directed cost functions can be solved similarly to the undirected case. Our algorithm starts with an $O(m\sqrt{n}\log n)$ preprocessing step that finds a 3-min-balanced reduced cost function. Using these reduced costs, every shortest path query can be solved in $O(m)$ time using an adaptation of Thorup's component hierarchy method. The balancing result is of independent interest, and gives the best currently known approximate balancing algorithm for the problem. |
SODA version
arXiv:2007.07975 |
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. |
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 Talk at the Aussois Combinatorial Optimization Workshop We present a layered-least squares (LLS) interior point method that solves a linear program of the form $\max\, c^\top x,\: Ax = b,\: x \geq 0,\: A \in \mathbb{R}^{m \times n}$ in $O(n^{2.5} \log n\log (\bar{\chi}^*_A+n))$ iterations. Here, $\bar{\chi}^*_A$ is defined as the minimum value of the condition number $\bar{\chi}_{A}$ achievable by a column rescaling. This improves on the running time $O(n^{3.5} \log (\bar{\chi}_A+n))$ of previous LLS methods. The result is achieved via a matroidal characterization of $\bar{\chi}^*_A$. In particular, we give an efficient algorithm to find a column scaling $D$ satisfying $\bar{\chi}_{AD} \leq n(\bar{\chi}^*)^3$. The improved $O(n^{2.5})$ dependence is achieved by a refined potential function based analysis for LLS algorithms in general. |
STOC version
arXiv:1912.06252 |
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. |
ITCS version
arXiv:1906:06686 |
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg, László A. Végh 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. |
STOC version
arXiv:1809.06266 |