Approximation Algorithms for Stochastic k-TSP.
Alina EneViswanath NagarajanRishi SaketPublished in: FSTTCS (2017)
Keyphrases
- approximation algorithms
- np hard
- approximation schemes
- special case
- traveling salesman problem
- worst case
- vertex cover
- minimum cost
- network design problem
- np hardness
- facility location problem
- set cover
- exact algorithms
- optimal solution
- ant colony optimization
- search space
- primal dual
- approximation ratio
- open shop
- constant factor approximation
- precedence constraints
- constant factor
- optimization problems
- disjoint paths
- combinatorial optimization
- approximation guarantees
- linear programming
- lower bound
- search algorithm