COMPUTER SCIENCE COLLOQUIUM

On the Curvature of the Central Path of Linear Programming Theory

Gregorio Malajovich Departamento de Matematica Aplicada Universidade Federal do Rio de Janeiro

Tuesday, March 16, 2004, at 14:15 Seminar Room

ABSTRACT

Interior point methods in Linear Programming are designed to follow the so-called central path. The actual performance of interior point methods seem better than known theoretical results. As a tentative of obtaining better complexity estimate, we give an upper bound on the total curvature of the central path.

This bound was obtained by reducing the curvature estimates to an integral geometry problem (expected number of intersections of the Gauss curve with a random plane), and then to the estimation of the number of roots of a certain polynomial system.

This is joint work with Jean-Pierre Dedieu (Univ. Paul Sabatier, Toulouse) and Mike Shub (Univ. of Toronto).

Host: Klaus Meer

---

SDU HOME | IMADA HOME | Previous Page

---

Last modified: March 16, 2004.

Joan Boyar (joan@imada.sdu.dk)