[For part I see Tech. Rep. SOL 81-16, Systems Optimization Laboratory, Oper. Res. Dept., Stanford Univ. (1981).] The deepest, or least shallow, cut ellipsoid method is a polynomial (time and space) method which finds an ellipsoid, representable by polynomial space integers, such that the maximal ellipsoidal distance relaxation method using this fixed ellipsoid is polynomial; this is equivalent to finding a linear transformation such that the maximal distance relaxation method of \textit{S. Agmon} [Can. J. Math. 6, 382-392 (1954; Zbl 0055.350)] and \textit{T. Motzkin} and \textit{I. J. Schoenberg} [ibid. 6, 393-404 (1954; Zbl 0055.350)] in this transformed space is polynomial. If perfect arithmetic is used, then the sequence of ellipsoids generated by the method converges to a set of ellipsoids, which share some of the properties of the classical Hessian at an optimum point of a function; and thus the ellipsoid method is quite analogous to a variable metric quasi-Newton method.