research
∙
11/21/2022
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
The simplex method for linear programming is known to be highly efficien...
share
research
∙
10/12/2022
A nearly optimal randomized algorithm for explorable heap selection
Explorable heap selection is the problem of selecting the nth smallest v...
research
∙
12/24/2021
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
The combinatorial diameter diam(P) of a polytope P is the maximum shorte...
research
∙
12/15/2020
On the Integrality Gap of Binary Integer Programs with Gaussian Data
For a binary integer program (IP) max c^𝖳 x, Ax ≤ b, x ∈{0,1}^n, where A...
research
∙
11/17/2020
Simple Iterative Methods for Linear Optimization over Convex Sets
We give simple iterative methods for computing approximately optimal pri...
research
∙
12/12/2019
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Following the breakthrough work of Tardos in the bit-complexity model, V...
research
∙
11/15/2017