Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 22:
== Computational complexity ==
The main problem with the method is that, in each step, we have to compute the center-of-gravity of a polytope. All the methods known so far for this problem require a number of arithmetic operations that is exponential in the dimension ''n.<ref name=":0" />{{Rp|___location=Sec.8.2.2}}'' Therefore, the method is not useful in practice when there are 5 or more dimensions.
== See also ==
The [[ellipsoid method]] can be seen as a modification of the center-of-gravity method in which, instead of maintaining the feasible polytope ''G<sub>t</sub>'', we maintain an ellipsoid that contains it. Computing the center-of-gravity of an ellipsoid is much easier than of a general polytope, and hence the ellipsoid method can usually be computed in polynomial time.
== References ==
| |||