Improved integrality gap upper bounds for TSP with distances one and two.

Matthias Mnich Tobias Mömke

Published in: CoRR (2013)

Keyphrases

tight upper and lower bounds
upper bound
integrality gap
lower bound
traveling salesman problem
upper and lower bounds
linear programming relaxation

valid inequalities
branch and bound
branch and bound algorithm
arbitrarily close
approximation algorithms
lower and upper bounds

randomly generated
genetic algorithm
combinatorial optimization
linear program
distance measure
np hard

search space
optimal solution
primal dual
lp relaxation
quadratic assignment problem
np hardness