Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP.
Aaron ArcherMohammadHossein BateniMohammad Taghi HajiaghayiHoward J. KarloffPublished in: FOCS (2009)
Keyphrases
- approximation algorithms
- prize collecting
- np hard
- steiner tree
- special case
- worst case
- traveling salesman problem
- vertex cover
- approximation ratio
- minimum cost
- primal dual
- minimum spanning tree
- combinatorial optimization
- optimal solution
- facility location
- genetic algorithm
- scheduling problem
- precedence constraints
- integer programming
- ant colony optimization
- lower bound