Worst-case performance of Wong's Steiner tree heuristic.
Alfredo Candia-VéjarHugo Bravo-AzlánPublished in: Discret. Appl. Math. (2006)
Keyphrases
- steiner tree
- worst case
- minimum spanning tree
- running times
- worst case analysis
- linear programming relaxation
- lower bound
- upper bound
- average case
- shortest path
- greedy algorithm
- optimal solution
- constraint satisfaction
- packing problem
- combinatorial optimization
- knapsack problem
- linear programming
- facility location
- dynamic programming
- computational complexity
- search algorithm
- spanning tree