The Matching Problem Has No Fully Polynomial Size Linear Programming Relaxation Schemes.
Gábor BraunSebastian PokuttaPublished in: IEEE Trans. Inf. Theory (2015)
Keyphrases
- linear programming relaxation
- polynomial size
- lower bound
- exponential size
- knapsack problem
- linear programming
- feasible solution
- branch and bound
- column generation
- knowledge compilation
- integer programming
- boolean functions
- integer program
- valid inequalities
- dnf formulas
- mixed integer programming
- bounded treewidth
- probability distribution
- cost function
- genetic algorithm