Improving the Integrality Gap for Multiway Cut.
Kristóf BércziKarthekeyan ChandrasekaranTamás KirályVivek MadanPublished in: IPCO (2019)
Keyphrases
- integrality gap
- linear programming relaxation
- linear program
- lower bound
- tight upper and lower bounds
- approximation algorithms
- arbitrarily close
- valid inequalities
- integer programming formulation
- lp relaxation
- linear programming
- primal dual
- knapsack problem
- feasible solution
- np hardness
- approximation guarantees
- low degree
- optimal solution
- objective function
- upper bound
- dnf formulas
- dynamic programming
- np hard
- special case