On the average number of steps of the simplex method of linear programming |
| |
| Authors: | Steve Smale |
| |
| Institution: | (1) Department of Mathematics, University of California, 94720 Berkeley, CA, USA |
| |
| Abstract: | The goal is to give some theoretical explanation for the efficiency of the simplex method of George Dantzig. Fixing the number
of constraints and using Dantzig's self-dual parametric algorithm, we show that the number of pivots required to solve a linear
programming problem grows in proportion to the number of variables on the average.
Supported in part by NSF Grant #MCS-8102262. |
| |
| Keywords: | Linear Programming Simplex Method Complexity Theory Algorithms Linear Complementarity Problem Path Following |
| 本文献已被 SpringerLink 等数据库收录！ |
