I am trying to understand why the ellipsoid method is not a strongly polynomial time algorithm for linear programming. Using wikipedia's definition, an algorithm runs in strongly-polynomial time if:

  1. The number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance.
  2. the space used by the algorithm is bounded by a polynomial in the size of the input.

My guess would be that, when choosing an initial ellipsoid, its volume may depend on the size (in bits) of the inputs, is this intuition correct?



Your Answer

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