LP Relaxation and Tree Packing for Minimum k-Cut.

Chandra Chekuri Kent Quanrud Chao Xu

Published in: SIAM J. Discret. Math. (2020)

Keyphrases

lp relaxation
integrality gap
linear programming
min cut
spanning tree
linear program
optimal solution
feasible solution
message passing
energy minimization
integer programming
knapsack problem
minimum cost
column generation
global constraints
integer program
valid inequalities
optimization problems
pairwise