Samarth Tiwari

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

    On the Complexity of Branching Proofs

  • Daniel Dadush
  • Samarth Tiwari
    • Categories Integer Programming Tags , , , , ,

    We consider the task of proving integer infeasibility of a bounded convex set K in R^n using a general branching proof system. In a general branching proof, one constructs a branching tree by adding an integer disjunction at each node, such that the leaves of the tree correspond to empty sets (i.e., K together with … Read more