Linear Programming Hierarchies Suffice for Directed Steiner Tree.
Zachary FriggstadJochen KönemannYoung Kun-KoAnand LouisMohammad ShadravanMadhur TulsianiPublished in: IPCO (2014)
Keyphrases
- linear programming
- steiner tree
- linear programming relaxation
- linear program
- minimum spanning tree
- facility location
- feasible solution
- integer programming
- column generation
- primal dual
- np hard
- shortest path
- dynamic programming
- quadratic programming
- objective function
- mixed integer
- semidefinite programming
- network flow
- valid inequalities
- special case
- optimal solution
- lower bound