I have always thought that the ellipsoid algorithm is an algorithm which can be used to solve LP in polynomial-time. However, what confuses me is the dependence on the ratio of volumes of the balls (one contained in the polytope, one containing it). I have tried finding some lecture notes online but none have explained the following problem.

Why is the ratio "small"? Ok, ok, I guess one could get an upper bound on the volume of the bigger ball based on the description length of the problem (is this actually what happens?). However, more problematic is the ball contained in the polytope. What if there is only one feasible solution?

Actually, I have watched a video lecture from MIT about this and at the end of the lecture, the lecturer showed a reduction from feasibility to optimisation in LP by "taking union the problem and its dual". But isn't this specifically very likely to result in LP which has only one feasible solution?

  • $\begingroup$ Have you read lecture notes on the ellipsoid algorithm? They are likely to be more detailed than video lectures. $\endgroup$ – Yuval Filmus Jul 25 '19 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.