1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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$
    – argentpepper
    Apr 11, 2014 at 17:11

0

Reset to default

Your Answer

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