SDP Integrality Gaps with Local ell_1-Embeddability.
Subhash KhotRishi SaketPublished in: FOCS (2009)
Keyphrases
- semi definite programming
- semidefinite programming
- lp relaxation
- half spaces
- mixed integer
- linear systems
- sparse representation
- linear programming
- extreme points
- real valued
- convex optimization
- truth table
- semidefinite
- linear program
- kernel matrix
- learning problems
- linear programming relaxation
- metric learning
- norm minimization
- semi supervised learning