Improved Approximation Algorithms for Weighted 2-Path Partitions.
Amotz Bar-NoyDavid PelegGeorge RabancaIvo ViganPublished in: ESA (2015)
Keyphrases
- approximation algorithms
- minimum cost
- np hard
- special case
- facility location problem
- worst case
- network design problem
- disjoint paths
- vertex cover
- primal dual
- np hardness
- approximation ratio
- set cover
- exact algorithms
- constant factor
- randomized algorithms
- approximation schemes
- undirected graph
- precedence constraints
- weighted sum
- dynamic programming
- open shop
- optimal solution