I have heard claims that for a certain class of optimization problems, one can re-write the problem as a linear-programming problem on the convex hull of the solution space of the original problem (even though enumerating the constraints that define the polytope could be computationally very expensive).

Is this correct? If so, what class of optimization problems can be re-written this way? and what references can I use to back up this claim?

  • 3
    $\begingroup$ Depending on how you define your optimization problem, any optimization problem that can be solved in polynomial time can be solved via linear programming, since the Linear Programming problem is P-complete. (However, even approximating a good solution to a given linear program remains P-complete.) $\endgroup$ Commented Apr 11, 2014 at 17:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.