Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality.
Lukasz KowalikMarcin MuchaPublished in: WADS (2009)
Keyphrases
- approximation algorithms
- triangle inequality
- np hard
- branch and bound algorithm
- quadratic assignment problem
- nearest neighbor
- similarity search
- traveling salesman problem
- distance function
- distance measure
- special case
- dissimilarity measure
- metric space
- integrality gap
- pre computed
- nearest neighbor search
- minimum cost
- distance metric
- worst case
- branch and bound
- edit distance
- exact algorithms
- combinatorial optimization
- similarity function
- similarity queries
- lower bound
- primal dual
- high dimensional
- constant factor
- undirected graph
- edge weights
- optimal solution
- approximation ratio
- similarity measure
- linear programming
- combinatorial optimization problems
- randomly generated
- integer programming
- upper bound
- feature space
- euclidean distance