Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husić, László A. Végh Accepted to 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 Strongly Polynomial Label-Correcting Algorithm for Linear Systems with Two Variables per Inequality
Zhuan Khye Koh, Bento Natura, László A. Végh We present a strongly polynomial label-correcting algorithm for solving the feasibility of linear systems with two variables per inequality (2VPI). The algorithm is based on the Newton-Dinkelbach method for fractional combinatorial optimization., and extends previous work of Madani (2002). We also obtain an acceleration of the Newton-Dinkelbach method for general fractional combinatorial optimization problems. |
arXiv:2004.08634 |
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 |