On the integrality gap of the subtour LP for the 1, 2-TSP.
Jiawei QianFrans SchalekampDavid P. WilliamsonAnke van ZuylenPublished in: Math. Program. (2015)
Keyphrases
- subtour elimination
- lp relaxation
- integrality gap
- linear programming
- linear program
- message passing
- optimal solution
- knapsack problem
- feasible solution
- integer programming
- energy minimization
- integer program
- valid inequalities
- traveling salesman problem
- integer programming formulation
- global constraints
- linear programming relaxation
- np hard
- column generation
- maximum a posteriori
- metaheuristic
- energy function
- objective function
- special case