The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem.
Samuel C. GutekunstDavid P. WilliamsonPublished in: CoRR (2017)
Keyphrases
- traveling salesman problem
- semidefinite
- integrality gap
- valid inequalities
- linear programming relaxation
- semidefinite programming
- combinatorial optimization
- interior point methods
- linear program
- ant colony optimization
- primal dual
- convex relaxation
- optimization problems
- sufficient conditions
- convex sets
- higher dimensional
- linear programming
- lp relaxation
- mixed integer programming
- knapsack problem