8 citations · 10 across the 11 of their papers we have counts for
4 papers · 1 filter
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…