Primal-Dual Approximation Algorithms for Feedback Problems.
Michel X. GoemansDavid P. WilliamsonPublished in: IPCO (1996)
Keyphrases
- approximation algorithms
- primal dual
- vertex cover
- linear programming problems
- semidefinite programming
- variational inequalities
- linear programming
- np hardness
- approximation schemes
- interior point
- special case
- affine scaling
- convex programming
- np hard
- convex optimization problems
- duality gap
- randomized algorithms
- worst case
- minimum cost
- interior point methods
- simplex algorithm
- saddle point
- interior point algorithm
- linear program
- convex optimization
- set cover
- convex functions
- quadratic program
- convergence rate
- algorithm for linear programming
- solving problems
- constant factor
- evolutionary algorithm
- combinatorial optimization
- feasible solution
- valid inequalities
- column generation