Matroids and integrality gaps for hypergraphic steiner tree relaxations.
Michel X. GoemansNeil OlverThomas RothvoßRico ZenklusenPublished in: STOC (2012)
Keyphrases
- steiner tree
- linear programming relaxation
- linear programming
- knapsack problem
- lower bound
- integer programming
- branch and bound
- column generation
- feasible solution
- mixed integer programming
- integer program
- valid inequalities
- submodular functions
- linear program
- optimal solution
- upper bound
- dynamic programming
- shortest path
- social networks
- semidefinite