[Formerly: Publ. I.R.M.A. Strasbourg, 1990, 413/S-21, p. 127-140.]

Beside the nice geometric proceeding a particular interest in this
method is derived from the following observation: In Karmarkar's
as well as in this algorithm one has to solve a linear equation
system of the form *A D*^{2}A^{T}*y* = *b*.
The solution of this
system is the most time consuming part in linear programs.
While in Karmarkar's method the entries of the diagonal
Matrix *D* are the coordinates of the iteration point, the
diagonal entries are either 0 or 1 in our method.
Hence throughout this paper *D* is a purely combinatorial
matrix which yields to reasonable numbers of rank one updates
of the corresponding Cholesky factor of *A D*^{2}A^{T}.
Moreover, the Cholesky factors become sparser than in Karmarkar's
approach.

Math. Inst. der Universität zu Köln

The following versions are available:

- PDF (178 K)
- PostScript (189 K)
- dvi version
- TeX version