An Improved Integrality Gap for Asymmetric TSP Paths.
Zachary FriggstadAnupam GuptaMohit SinghPublished in: Math. Oper. Res. (2016)
Keyphrases
- integrality gap
- traveling salesman problem
- valid inequalities
- linear programming relaxation
- linear program
- ant colony optimization
- arbitrarily close
- combinatorial optimization
- search space
- approximation algorithms
- lower bound
- optimal solution
- shortest path
- genetic algorithm
- np hard
- linear programming
- np hardness
- distributed systems
- cost function
- search algorithm
- randomly generated problems
- low degree