*(English)*Zbl 0708.90049

Summary: [For the entire collection see Zbl 0669.00026.]

This chapter presents an algorithm that works simultaneously on primal and dual linear programming problems and generates a sequence of pairs of their interior feasible solutions. Along the sequence generated, the duality gap converges to zero at least linearly with a global convergence ratio (1-$\eta $ /n); each iteration reduces the duality gap by at least $\eta $ /n. Here n denotes the size of the problems and $\eta $ a positive number depending on initial interior feasible solutions of the problems. The algorithm is based on an application of the classical logarithmic barrier function method to prime and dual linear programs, which has recently been proposed and studied by *N. Megiddo* [ibid., 131-158 (1989; Zbl 0687.90056)].