Comment on “P = NP” Polynomial-Sized LP Models for Hard CopsparentComments−zelos3yYou can solve the integer case via branch and bound: solving the relaxed linear problem and then in a tree search constraining integer variables to be 0/1. Potentially they're doing something equivalent to that?−coliveira3yBut this leads to an exponential time algorithm.−throw_pm233yIf the claim were true that the solution is always integer, then one could use a poly-time LP solver.
Comments
You can solve the integer case via branch and bound: solving the relaxed linear problem and then in a tree search constraining integer variables to be 0/1. Potentially they're doing something equivalent to that?
But this leads to an exponential time algorithm.
If the claim were true that the solution is always integer, then one could use a poly-time LP solver.