An improved LP-based approximation for steiner tree.

Jaroslaw Byrka Fabrizio Grandoni Thomas Rothvoß Laura Sanità

Published in: STOC (2010)

Keyphrases

steiner tree
linear programming relaxation
linear programming
feasible solution
linear program
shortest path
minimum spanning tree
facility location
lower bound
knapsack problem
optimal solution
evolutionary algorithm
np hard