Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs.
Piotr BermanGrigory YaroslavtsevPublished in: APPROX-RANDOM (2012)
Keyphrases
- approximation algorithms
- primal dual
- network design
- planar graphs
- vertex cover
- undirected graph
- network design problem
- np hard
- special case
- communication networks
- worst case
- minimum cost
- network architecture
- edge weights
- valid inequalities
- weighted graph
- graph structure
- lower bound
- genetic algorithm
- convergence rate
- linear program
- linear programming
- minimum weight
- upper bound