|
|||||
|
|
On the Curvature of the Central Path of Linear Programming Theory |
|
| Authors: | Jean-Pierre Dedieu Gregorio Malajovich Mike Shub |
| Institution: | (1) MIP, Departement de Mathematique, Universite Paul Sabatier, 31062 Toulouse cedex 04, France;(2) Departamento de Matematica Aplicada, Universidade Federal de Rio de Janeiro, Caixa Postal 68530, CEP 21945-970, Rio de Janeiro, RJ, Brazil;(3) Department of Mathematics, University of Toronto, 100 St. George Street, Toronto, Ontario M5S 3G3, Canada |
| Abstract: | We prove a linear bound on the average total curvature of the central path of linear programming theory in terms of the number of independent variables of the primal problem, and independent of the number of constraints. |
| Keywords: | Interior point methods Central path Curvature Integral geometry Multihomogeneous Bezout theorem |
| 本文献已被 SpringerLink 等数据库收录！ | |