Sophie Huiberts

On the Integrality Gap of Binary Integer Programs with Gaussian Data

  • Sander Borst
  • Daniel Dadush
  • Sophie Huiberts
  • Samarth Tiwari
    • Categories Integer Programming Tags , ,

    For a binary integer program (IP) $\max c^\T x, Ax \leq b, x \in \{0,1\}^n$, where $A \in \R^{m \times n}$ and $c \in \R^n$ have independent Gaussian entries and the right-hand side $b \in \R^m$ satisfies that its negative coordinates have $\ell_2$ norm at most $n/10$, we prove that the gap between the value … Read more

    Simple Iterative Methods for Linear Optimization over Convex Sets

  • Daniel Dadush
  • Christopher Hojny
  • Sophie Huiberts
  • Stefan Weltge
    • Categories Linear Programming Tags , ,

    We give simple iterative methods for computing approximately optimal primal and dual solutions for the problem of maximizing a linear functional over a convex set $K$ given by a separation oracle. In contrast to prior work, our algorithms directly output primal and dual solutions and avoid a common requirement of binary search on the objective … Read more