A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP.

Anna Karlin Nathan Klein Shayan Oveis Gharan

Published in: CoRR (2021)

Keyphrases

integrality gap
subtour elimination
lp relaxation
traveling salesman problem
valid inequalities
lower bound
linear programming relaxation
linear program

linear programming
optimal solution
message passing
upper bound
primal dual
energy minimization
np hard
ant colony optimization

combinatorial optimization
feasible solution
knapsack problem
arbitrarily close
optimization problems
integer programming
worst case

column generation
mixed integer programming
global constraints
dynamic programming
solution quality
branch and bound algorithm
distributed systems