Sophie Huiberts

activity

20172025

most citedUpper and Lower Bounds on the Smoothed Complexity of the Simplex Method

1 citations · 2 across the 8 of their papers we have counts for

collaborators

Showing math.OCShow all

3 papers · 1 filter

math.OC2020

On the Integrality Gap of Binary Integer Programs with Gaussian Data

Sander Borst, Daniel Dadush, Sophie Huiberts +1

For a binary integer program (IP) $max c^{T} x, A x \leq b, x \in {0, 1}^{n}$ , where $A \in R^{m \times n}$ and $c \in R^{n}$ have independent Gaussian…

math.OC2020

A Simple Method for Convex Optimization in the Oracle Model

Daniel Dadush, Christopher Hojny, Sophie Huiberts +1

We give a simple and natural method for computing approximately optimal solutions for minimizing a convex function $f$ over a convex set $K$ given by a separation oracle. Our metho…

math.OC2019

A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

Daniel Dadush, Sophie Huiberts, Bento Natura +1

Following the breakthrough work of Tardos in the bit-complexity model, Vavasis and Ye gave the first exact algorithm for linear programming in the real model of computation with ru…