Contents

1. Recent Progress and New Directions

Some Recent Results on Convex Polytopes

CARL

W.

LEE

Probabilistic Analysis of the Simplex Method

KARL HEINZ BORGWARDT

On Solving the Linear Programming Problem Approximately

NIMROD MEGIDDO

Riemannian Geometry Underlying Interior-Point Methods for Linear

Programming

NARENDRA KARMARKAR

Steepest Descent, Linear Programming, and Hamiltonian Flows

A. M. BLOCH

2. Interior-Point Methods for Linear Programming

An O(n3L) Potential Reduction Algorithm for Linear Programming

YINYU YE

I. I. Dikin's Convergence Result for the Affine-Scaling Algorithm

R. J. VANDERBEI

AND

J. C. LAGARIAS

Phase 1 Search Directions for a Primal-Dual Interior Point Method for

Linear Programming

IRVIN J. LUSTIG

Some Results Concerning Convergence of the Affine Scaling Algorithm

EARL R. BARNES

Dual Ellipsoids and Degeneracy in the Projective Algorithm for Linear

Programming

KURT M. ANSTREICHER