8 citations · 10 across the 11 of their papers we have counts for
15 papers
Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin Husić, Wenzheng Li +2
For any , we give a simple, deterministic -approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also co…
An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem
Satoru Fujishige, Tomonari Kitahara, László A. Végh
We consider the minimum-norm-point (MNP) problem over polyhedra, a well-studied problem that encompasses linear programming. We present a general algorithmic framework that combine…
On the Correlation Gap of Matroids
Edin Husić, Zhuan Khye Koh, Georg Loho +1
A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the per…
Interior point methods are not worse than Simplex
Xavier Allamigeon, Daniel Dadush, Georg Loho +2
We develop a new `subspace layered least squares' interior point method (IPM) for solving linear programs. Applied to an -variable linear program in standard form, the iteration…
Tractable Fragments of the Maximum Nash Welfare Problem
Jugal Garg, Edin Husić, Aniket Murhekar +1
We study the problem of maximizing Nash welfare (MNW) while allocating indivisible goods to asymmetric agents. The Nash welfare of an allocation is the weighted geometric mean of a…
On Circuit Diameter Bounds via Circuit Imbalances
Daniel Dadush, Zhuan Khye Koh, Bento Natura +1
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 diam…
Circuit imbalance measures and linear programming
Farbod Ekbatani, Bento Natura, László A. Végh
We study properties and applications of various circuit imbalance measures associated with linear spaces. These measures describe possible ratios between nonzero entries of support…
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 spe…
On complete classes of valuated matroids
Edin Husić, Georg Loho, Ben Smith +1
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…
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 comple…
Directed Shortest Paths via Approximate Cost Balancing
James B. Orlin, László A. Végh
We present an algorithm for all-pairs shortest paths computations in a directed graph with nodes, arcs, and nonnegative integer arc costs. This matches the complexi…
An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
Daniel Dadush, Zhuan Khye Koh, Bento Natura +1
We present an accelerated, or 'look-ahead' version of the Newton-Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceler…
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Daniel Dadush, Sophie Huiberts, Bento Natura +1
Following the breakthrough work of Tardos in the bit-complexity model, Vavasis and Ye gave the first exact algorithm for linear programming in the real model of computation with ru…
On Submodular Search and Machine Scheduling
Robbert Fokkink, Thomas Lidbetter, László A. Végh
Suppose some objects are hidden in a finite set of hiding places which must be examined one-by-one. The cost of searching subsets of is given by a submodular function and t…
A Definition for Fine Tuning in Analogy to the Chaos
Zs. Hetesi, L. Végh
Anthropic principles were grown from the problem of fine tuning. Although anthropic principles have been discussed in cosmology for years there is no exact definition for fine tuni…