3 papers
cs.GT2026
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…
math.OC2025
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…
math.CO2024
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…