Linear programming relaxations of maxcut.
Wenceslas Fernandez de la VegaClaire Kenyon-MathieuPublished in: SODA (2007)
Keyphrases
- linear programming relaxation
- lower bound
- knapsack problem
- linear programming
- column generation
- branch and bound
- integer programming
- upper bounding
- feasible solution
- mixed integer programming
- integer program
- valid inequalities
- branch and bound algorithm
- optimization problems
- neural network
- upper bound
- cutting plane
- dynamic programming
- optimal solution
- np hard