On the Combinatorial Lower Bound for the Extension Complexity of the Spanning Tree Polytope.
Kaveh KhoshkhahDirk Oliver TheisPublished in: CoRR (2017)
Keyphrases
- spanning tree
- lower bound
- worst case
- minimum cost
- upper bound
- minimum spanning tree
- minimum spanning trees
- minimum weight
- np hard
- lattice points
- branch and bound algorithm
- objective function
- computational complexity
- knapsack problem
- optimal solution
- edge weights
- lower and upper bounds
- undirected graph
- weighted graph
- approximation algorithms
- branch and bound
- facet defining inequalities