Volume 3 (2007) Article 8 pp. 159-177
Removing Degeneracy May Require a Large Dimension Increase
by
Published: September 26, 2007
The result of this paper can be regarded as an indication that the problem of removing degeneracies has no simple “abstract” solution. We consider LP-type problems, a successful axiomatic framework for optimization problems capturing, e.g., linear programming and the smallest enclosing ball of a point set. For infinitely many integers $D$ we construct a $D$-dimensional LP-type problem such that in order to remove degeneracies from it, we have to increase the dimension to at least $(1+\epsilon)D$, where $\epsilon>0$ is an absolute constant.