Subsampling Mathematical Relaxations and Average-case Complexity.

Boaz Barak Moritz Hardt Thomas Holenstein David Steurer

Published in: SODA (2011)

Keyphrases

average case complexity
lower bound
average case
np hard
upper bound
linear programming
worst case
branch and bound
state space
objective function
shortest path
multistage
uniform distribution
search algorithm
convex relaxation
semidefinite
optimal solution