An Improved Integrality Gap for Asymmetric TSP Paths.
Zachary FriggstadAnupam GuptaMohit SinghPublished in: IPCO (2013)
Keyphrases
- integrality gap
- traveling salesman problem
- valid inequalities
- linear programming relaxation
- linear program
- optimal solution
- approximation algorithms
- arbitrarily close
- ant colony optimization
- lower bound
- linear programming
- optimization problems
- combinatorial optimization
- np hard
- genetic algorithm
- knapsack problem
- integer programming formulation
- column generation
- search space
- shortest path
- integer programming
- lp relaxation
- low degree
- evolutionary algorithm
- finite number
- quadratic assignment problem
- np hardness
- energy function