That is far beyond my knowledge of graph theory and convex optimization but the Wikipedia article [1] suggests that is a general problem of the method and it on

That is far beyond my knowledge of graph theory and convex optimization but the Wikipedia article [1] suggests that is a general problem of the method and it only works well for low dimensional data. [1] https://en.wikipedia.org/wiki/Ellipsoid_method#Performance https://en.wikipedia.org/wiki/Ellipsoid_method#Performance