Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes.
Daiki HoshikaEiji MiyanoPublished in: IEICE Trans. Fundam. Electron. Commun. Comput. Sci. (2016)
Keyphrases
- approximation algorithms
- steiner tree
- packing problem
- np hard
- undirected graph
- special case
- minimum spanning tree
- facility location
- vertex cover
- minimum cost
- worst case
- shortest path
- approximation ratio
- linear programming relaxation
- constant factor
- set cover
- primal dual
- disjoint paths
- constant factor approximation
- integer programming
- np complete
- lower bound
- optimal solution