An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree.
Jochen KönemannSina Sadeghian SadeghabadLaura SanitàPublished in: FOCS (2013)
Keyphrases
- worst case
- steiner tree
- prize collecting
- cost function
- optimal solution
- np hard
- hybrid algorithm
- convergence rate
- convex hull
- combinatorial optimization
- linear programming
- dynamic programming
- particle swarm optimization
- search space
- special case
- graph structure
- weighted graph
- packing problem
- edge weights
- minimum spanning tree
- lower bound
- objective function