A strongly polynomial algorithm for linear programs with at most two non-zero entries per row or column
Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, and László A. Végh STOC 2024 We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Megiddo (SICOMP '83) and Végh (MOR '17) respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS '22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum (ORL '04), the same bound applies to any linear program with at most two non-zeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices. Our approach is black-box and can be applied to any log-barrier path following method. |
STOC version
|
Approximating Competitive Equilibrium by Nash Welfare
Jugal Garg, Yixin Tao, László A. Végh Accepted to SODA 2025
We explore the relationship between two popular concepts on allocating divisible items: competitive equilibrium (CE) and allocations with maximum Nash welfare, i.e., allocations where the weighted geometric mean of the utilities is maximal. When agents have homogeneous concave utility functions, these two concepts coincide: the classical Eisenberg-Gale convex program that maximizes Nash welfare over feasible allocations yields a competitive equilibrium. However, these two concepts diverge for non-homogeneous utilities. From a computational perspective, maximizing Nash welfare amounts to solving a convex program for any concave utility functions, computing CE becomes PPAD-hard already for separable piecewise linear concave (SPLC) utilities.
|
arXiv:2402.09994 |
A First Order Method for Linear Programming Parameterized by Circuit Imbalance
Richard Cole, Christoph Hertrich, Yixin Tao, László A. Végh IPCO 2024 Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. We introduce a first order approach for LP optimization with a convergence rate depending polynomially on the circuit imbalance measure, which is a geometric parameter of the constraint matrix, and depending logarithmically on the right hand side, capacity, and cost vectors. This provides much stronger convergence guarantees than the previous known methods. For example, if the constraint matrix is totally unimodular, we obtain polynomial-time algorithms. Our approach is based on a fast gradient method due to Necoara, Nesterov, and Glineur (Math. Prog. 2019); this algorithm is called repeatedly in a framework that gradually fixes variables to the boundary. This technique is based on a new approximate version of Tardos's method, that was used to obtain a strongly polynomial algorithm for combinatorial LPs (Oper. Res. 1986). |
arXiv:2311.01959 |
Faster Ascending Auctions via Polymatroid Sum
Katharina Eickhoff, Britta Peis, Niklas Rieken, Laura Vargas Koch, László A. Végh WINE 2023 We consider ascending auctions for finding Walrasian equilibria in markets with indivisible items and gross substitutes valuation functions. Each price increase step in the auction algorithm requires finding an inclusion-wise minimal maximal overdemanded set at the current prices. This can be formulated as a submodular function minimization problem. We observe that minimizing this submodular function corresponds to a polymatroid sum problem, and using this viewpoint, we give a fast and simple push-relabel algorithm for finding the minimal maximal overdemanded set. |
arXiv:2310.08454 |
Mode Connectivity in Auction Design
Christoph Hertrich, Yixin Tao, László A. Végh NeurIPS 2023 Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt to theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and a generalized version for affine maximizer auctions. We prove that they satisfy mode connectivity, i.e., locally optimal solutions are connected by a simple, piecewise linear path such that every solution on the path is almost as good as one of the two local optima. Mode connectivity has been recently investigated as an intriguing empirical and theoretically justifiable property of neural networks used for prediction problems. Our results give the first such analysis in the context of differentiable economics, where neural networks are used directly for solving non-convex optimization problems. |
NeurIPS version
arXiv:2305.11005 |
Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, Jan Vondrák 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$.
|
arXiv:2211.03883 |
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. |
arXiv:2206.08810 |
On finding exact solutions of linear programs in the oracle model
Daniel Dadush, Giacomo Zambelli, László A. Végh SODA 2022
|
SODA version
|
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. |
SODA version
arXiv:2107:05700 |
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. |
STOC version
arXiv:2009.14793 |
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 |
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 |