|
|||||
|
|
A polynomial method of approximate centers for linear programming |
|
| Authors: | C. Roos J. -Ph. Vial |
| Affiliation: | (1) Department of Mathematics and Computer Science, Delft University of Technology, P.O. Box 356, 2600 AJ Delft, Netherlands;(2) Department of Commerical and Industrial Economics, University of Geneve, CH-1211 Geneve 4, Switzerland |
| Abstract: | We present a path-following algorithm for the linear programming problem with a surprisingly simple and elegant proof of its polynomial behaviour. This is done both for the problem in standard form and for its dual problem. We also discuss some implementation strategies.This author completed this work under the support of the research grant No. 1467086 of the Fonds National Suisses de la Recherche Scientifique. |
| Keywords: | Interior-point method linear programming Karmarkar's method polynomial-time algorithm logarithmic barrier function path-following method |
| 本文献已被 SpringerLink 等数据库收录！ | |