Subexponential lower bounds for randomized pivoting rules for the simplex algorithm.
Oliver FriedmannThomas Dueholm HansenUri ZwickPublished in: STOC (2011)
Keyphrases
- simplex algorithm
- lower bound
- simplex method
- linear programming
- linear program
- primal dual
- upper bound
- randomly generated
- network simplex algorithm
- interior point methods
- linear programming problems
- objective function
- branch and bound
- branch and bound algorithm
- np hard
- optimal solution
- lower and upper bounds
- feasible solution
- denoising
- linear programming relaxation
- multistage
- interior point