52 citations · 131 across the 29 of their papers we have counts for
11 papers · 1 filter
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: , where the polyhedron is given by a separation oracle. We…
From approximate to exact integer programming
Daniel Dadush, Friedrich Eisenbrand, Thomas Rothvoss
Approximate integer programming is the following: For a convex body , either determine whether is empty, or find an integer point in…
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…
Integrality Gaps for Random Integer Programs via Discrepancy
Sander Borst, Daniel Dadush, Dan Mikulincer
We prove new bounds on the additive gap between the value of a random integer program with constraints and that of its linear programming…
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…
On the Integrality Gap of Binary Integer Programs with Gaussian Data
Sander Borst, Daniel Dadush, Sophie Huiberts +1
For a binary integer program (IP) , where and have independent Gaussian…