On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique.
Reuven Bar-YehudaDror RawitzPublished in: SIAM J. Discret. Math. (2005)
Keyphrases
- primal dual
- linear programming
- linear program
- convex optimization
- affine scaling
- interior point methods
- linear programming problems
- convergence rate
- approximation algorithms
- interior point algorithm
- variational inequalities
- simplex algorithm
- semidefinite programming
- infeasible interior point
- algorithm for linear programming
- convex programming
- simplex method
- dynamic programming
- dual formulation
- duality gap
- interior point
- search direction
- convex functions
- convex optimization problems
- high resolution
- objective function
- multiscale