Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program.

Daniel Prusa Tomás Werner

Published in: SIAM J. Optim. (2019)

Keyphrases

lp relaxation
linear program
integer program
linear programming
knapsack problem
np hard problems
nonlinear programming
message passing
column generation
np hard
optimal solution
genetic algorithm
dynamic programming
state space
combinatorial optimization