Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a linear programming problem where the polytope is described as a convex hull of an exponential number ($2^d$) of points in d-dimensional space. What could be an approach? Do you first identify the set of vertices from the $2^d$ points and check which vertex maximizes the objective? Is there an efficient algorithm to identify the set of vertices from the given set of $2^d$ points?

share|improve this question
This might be useful: mathoverflow.net/questions/97131/… –  Yoav Kallus Apr 12 '13 at 22:05
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.