Constant Factor Approximation for ATSP with Two Edge Weights.
Ola SvenssonJakub TarnawskiLászló A. VéghPublished in: CoRR (2015)
Keyphrases
- edge weights
- constant factor approximation
- approximation algorithms
- np hard
- undirected graph
- weighted graph
- bipartite graph
- traveling salesman problem
- spanning tree
- closest string
- minimum cost
- shortest path
- directed graph
- satisfy the triangle inequality
- special case
- directed acyclic graph
- scheduling problem
- graph structure
- optimal solution
- triangle inequality