A lower bound of 8/(7+(1/k)-1) on the integrality ratio of the Calinescu-Karloff-Rabani relaxation for multiway cut.
Ari FreundHoward J. KarloffPublished in: Inf. Process. Lett. (2000)
Keyphrases
- integrality gap
- linear programming relaxation
- tight upper and lower bounds
- lower bound
- arbitrarily close
- upper bound
- branch and bound
- lp relaxation
- upper and lower bounds
- knapsack problem
- linear programming
- finite number
- np hard
- lower and upper bounds
- branch and bound algorithm
- mixed integer programming
- worst case
- optimal solution
- valid inequalities
- column generation
- feasible solution
- integer programming
- lagrangian relaxation
- objective function
- extreme points
- linear program
- tree structures
- approximation algorithms
- lower bounding
- families of valid inequalities
- integer program
- cutting plane
- message passing
- combinatorial optimization