The ellipsoid algorithm using parallel cuts (Q1315450): Difference between revisions

The paper presents a new variant of the ellipsoid algorithm using parallel cuts. The geometrical idea is described as follows: If the ratio of the distance between the parallel cuts under consideration and the corresponding radius of the current ellipsoid is less than or equal to some constant, the situation is called ``canonical''. In this canonical situation the volume of the next ellipsoid decreases by a factor \(\leq\exp \bigl(-{1\over 2(n+2)}\bigr)\). Noncanonical cases are reduced to canonical ones in a higher-dimensional space by adding an extra constraint. A complete complexity analysis and variants of the algorithm are supplied.