Arrow Research search

Author name cluster

László A. Végh

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

24 papers
2 author rows

Possible papers

24

STOC Conference 2024 Conference Paper

A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column

  • Daniel Dadush
  • Zhuan Khye Koh
  • Bento Natura
  • Neil Olver
  • László A. Végh

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 Végh ‍(MOR ’17) and Megiddo ‍(SICOMP ’83), 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) by 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 and extreme rays. Our approach is black-box and can be applied to any log-barrier path-following method.

Details

STOC Conference 2023 Conference Paper

Approximating Nash Social Welfare by Matching and Local Search

  • Jugal Garg
  • Edin Husic
  • Wenzheng Li
  • László A. Végh
  • Jan Vondrák

For any >0, we give a simple, deterministic (4+)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. The previous best approximation factor was 380 via a randomized algorithm. 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 (ω + 2 + ) -approximation if the ratio between the largest weight and the average weight is at most ω. We also show that the 12-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 12-EFX and a (8+)-approximation to the symmetric NSW problem under submodular valuations. The previous best approximation factor under 12-EFX was linear in the number of agents.

Details

NeurIPS Conference 2023 Conference Paper

Mode Connectivity in Auction Design

  • Christoph Hertrich
  • Yixin Tao
  • László A. Végh

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.

PDF Details

SODA Conference 2022 Conference Paper

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 goods 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.

Details

FOCS Conference 2022 Conference Paper

Interior point methods are not worse than Simplex

  • Xavier Allamigeon
  • Daniel Dadush
  • Georg Loho
  • Bento Natura
  • László A. Végh

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound $O(2^{n}n^{15}\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^{15}\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. From the existence of a line segment in the wide neighborhood we derive strong implications on the structure of the corresponding segment of the central path. Our algorithm is able to detect this structure from the local geometry at the current iterate, and constructs a step direction that descends along this segment. The bound $O(n^{15}\log n)$ that applies for arbitrarily long line segments is derived from a combinatorial progress measure. Our algorithm falls into the family of layered least squares interior point methods introduced by Vavasis and Ye (Math. Prog. 1996). In contrast to previous layered least squares methods that partition the kernel of the constraint matrix into coordinate subspaces, our method creates layers based on a general subspace providing more flexibility. Our result also implies the same bound on the number of iterations of the trust region interior point method by Lan, Monteiro, and Tsuchiya (SIOPT 2009).

Details

SODA Conference 2022 Conference Paper

On complete classes of valuated matroids

  • Edin Husic
  • 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 exhibit a family of valuated matroids that are not R-minor 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.

Details

SODA Conference 2022 Conference Paper

On finding exact solutions of linear programs in the oracle model

  • Daniel Dadush
  • László A. Végh
  • Giacomo Zambelli

We consider linear programming in the oracle model: min c T x s. t. x ∊ P, where the polyhedron P = { x ∊ ℝ n: Ax ≤ b } is given by a separation oracle that returns violated inequalities from the system Ax ≤ b. We present an algorithm that finds exact primal and dual solutions using O(n 2 log( n/δ )) oracle calls and O(n 4 log ( n/δ ) + n 6 log log(1/ δ )) arithmetic operations, where δ is a geometric condition number associated with the system ( A, b ). These bounds do not depend on the cost vector c. The algorithm works in a black box manner, requiring a subroutine for approximate primal and dual solutions; the above running times are achieved when using the cutting plane method of Jiang, Lee, Song, and Wong (STOC 2020) for this subroutine. Whereas approximate solvers may return primal solutions only, we develop a general framework for extracting dual certificates based on the work of Burrell and Todd (Math. Oper. Res. 1985). Our algorithm works in the real model of computation, and extends results by Grötschel, Lovász, and Schrijver (Prog. Comb. Opt. 1984), and by Frank and Tardos (Combinatorica 1987) on solving LPs in the bit-complexity model. We show that under a natural assumption, simultaneous Diophantine approximation in these results can be avoided.

Details

STOC Conference 2021 Conference Paper

Approximating Nash social welfare under rado valuations

  • Jugal Garg
  • Edin Husic
  • László A. Végh

We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to n agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of the agents’ valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. Subsequent work has obtained constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and O ( n )-approximation algorithms for subadditive valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. 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.

Details

SODA Conference 2021 Conference Paper

Directed Shortest Paths via Approximate Cost Balancing

  • James B. Orlin
  • László A. Végh

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 [26] 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 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.

Details

FOCS Conference 2020 Conference Paper

Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers

  • Daniel Dadush
  • Bento Natura
  • László A. Végh

In breakthrough work, Tardos (Oper. Res. '86) gave a proximity based framework for solving linear programming (LP) in time depending only on the constraint matrix in the bit complexity model. In Tardos's framework, one reduces solving the LP min(c, x), Ax=b, x ≥ 0, A Z m×n, to solving O(nm) LPs in A having small integer coefficient objectives and right-hand sides using any exact LP algorithm. This gives rise to an LP algorithm in time poly (n, m log Δ A ), where Δ A is the largest subdeterminant of A. A significant extension to the real model of computation was given by Vavasis and Ye (Math. Prog. '96), giving a specialized interior point method that runs in time poly (n, m, log χ̑ A ), depending on Stewart's χ̑ A, a well-studied condition number. In this work, we extend Tardos's original framework to obtain such a running time dependence. In particular, we replace the exact LP solves with approximate ones, enabling us to directly leverage the tremendous recent algorithmic progress for approximate linear programming. More precisely, we show that the fundamental “accuracy” needed to exactly solve any LP in A is inverse polynomial in n and log χ̑ A. Plugging in the recent algorithm of van den Brand (SODA '20), our method computes an optimal primal and dual solution using O(mn ω+1+0(1) log(χ̑ A +n)) arithmetic operations, outperforming the specialized interior point method of Vavasis and Ye and its recent improvement by Dadush et al (STOC '20). By applying the preprocessing algorithm of the latter paper, the dependence can also be reduced from χ̑ A to χ̑ A *, the minimum value of χ̑ AD attainable via column rescalings. Our framework is applicable to achieve the poly (n, m, log χ̑ A *) bound using essentially any weakly polynomial LP algorithm, such as the ellipsoid method. At a technical level, our framework combines together approximate LP solutions to compute exact ones, making use of constructive proximity theorems-which bound the distance between solutions of “nearby” LPs-to keep the required accuracy low.

Details

STOC Conference 2017 Conference Paper

A simpler and faster strongly polynomial algorithm for generalized flow maximization

  • Neil Olver
  • László A. Végh

We present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given very recently by Végh; our new algorithm is much simpler, and much faster. The complexity bound O (( m + n log n ) mn log( n 2 / m )) improves on the previous estimate obtained by Végh by almost a factor O ( n 2 ). 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.

Details

FOCS Conference 2013 Conference Paper

Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs

  • Joseph Cheriyan
  • László A. Végh

We present a 6-approximation algorithm for the minimum-cost k-node connected spanning sub graph problem, assuming that the number of nodes is at least k3(k-1)+k. We apply a combinatorial preprocessing, based on the Frank-Tardos algorithm for k-out connectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant-factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of k.

Details

FOCS Conference 2012 Conference Paper

Concave Generalized Flows with Applications to Market Equilibria

  • László A. Végh

We consider a nonlinear extension of the generalized network How model, with the How leaving an arc being an increasing concave function of the How entering it, as proposed by Truemper [1] and Shigeno [2]. We give a polynomial time combinatorial algorithm for solving corresponding How maximization problems, finding an ε-approximate solution in O(m(m + log n) log(MUm/ε)) arithmetic operations and value oracle queries, where M and U are upper bounds on simple parameters. This also gives a new algorithm for linear generalized Hows, an efficient, purely scaling variant of the Fat-Path algorithm by Goldberg, Plotkin and Tardos [3], not using any cycle cancellations. We show that this general convex programming model serves as a common framework for several market equilibrium problems, including the linear Fisher market model and its various extensions. Our result immediately provides combinatorial algorithms for various extensions of these market models. This includes nonsymmetric Arrow-Debreu Nash bargaining, settling an open question by Vazirani [4].

Details

STOC Conference 2012 Conference Paper

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

  • László A. Végh

A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective ∑ ij∈E C ij (f ij ) over feasible flows f, where on every arc ij of the network, C ij is a convex function. We give a strongly polynomial algorithm for finding an exact optimal solution for a broad class of such problems. The key characteristic of this class is that an optimal solution can be computed exactly provided its support. This includes separable convex quadratic objectives and also certain market equilibria problems: Fisher's market with linear and with spending constraint utilities. We thereby give the first strongly polynomial algorithms for separable quadratic minimum-cost flows and for Fisher's market with spending constraint utilities, settling open questions posed e.g. in [15] and in [35], respectively. The running time is O(m 4 log m) for quadratic costs, O(n 4 +n 2 (m+n log n) log n) for Fisher's markets with linear utilities and O(mn 3 +m 2 (m+n log n) log m) for spending constraint utilities.

Details

FOCS Conference 2012 Conference Paper

The Cutting Plane Method Is Polynomial for Perfect Matchings

  • Karthekeyan Chandrasekaran
  • László A. Végh
  • Santosh S. Vempala

The cutting plane approach to optimal matchings has been discussed by several authors over the past decades, and its rate of convergence has been an open question. We prove that the cutting plane approach using Edmonds' blossom inequalities converges in polynomial time for the minimum-cost perfect matching problem. Our main insight is an LP-based method to select cutting planes. This cut selection procedure leads to a sequence of intermediate linear programs with a linear number of constraints whose optima are half-integral and supported by a disjoint union of odd cycles and edges. This structural property of the optima is instrumental in finding violated blossom inequalities (cuts) in linear time. Moreover, the number of cycles in the support of the half-integral optima acts as a potential function to show efficient convergence to an integral solution.

Details