Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm |
| |
Authors: | Nimrod Megiddo |
| |
Institution: | (1) The IBM Almaden Research Center, 650 Harry Road, 95120 San José, CA, USA;(2) Department of Statistics, Tel Aviv University, Tel Aviv, Israel |
| |
Abstract: | In this paper we analyze the average number of steps performed by the self-dual simplex algorithm for linear programming, under the probabilistic model of spherical symmetry. The model was proposed by Smale. Consider a problem ofn variables withm constraints. Smale established that for every number of constraintsm, there is a constantc(m) such that the number of pivot steps of the self-dual algorithm, (m, n), is less thanc(m)(lnn)
m(m+1)
. We improve upon this estimate by showing that (m, n) is bounded by a function ofm only. The symmetry of the function inm andn implies that (m, n) is in fact bounded by a function of the smaller ofm andn.
Parts of this research were done while the author was visiting Stanford University, XEROX- PARC, Carnegie-Mellon University and Northwestern University and was supported in part by the National Science Foundation under Grants MCS-8300984, ECS-8218181 and ECS-8121741. |
| |
Keywords: | Probabilistic analysis self-dual simplex spherical symmetry |
本文献已被 SpringerLink 等数据库收录! |
|