Shinji Mizuno, Nimrod Megiddo, et al.
Journal of Complexity
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 of n variables with m constraints. Smale established that for every number of constraints m, there is a constant c(m) such that the number of pivot steps of the self-dual algorithm, ρ(m, n), is less than c(m)(ln n)m(m+1). We improve upon this estimate by showing that ρ(m, n) is bounded by a function of m only. The symmetry of the function in m and n implies that ρ(m, n) is in fact bounded by a function of the smaller of m and n. © 1986 The Mathematical Programming Society, Inc.
Shinji Mizuno, Nimrod Megiddo, et al.
Journal of Complexity
Daniela Pucci De Farias, Nimrod Megiddo
NeurIPS 2003
Tomás Feder, Nimrod Megiddo, et al.
Theoretical Computer Science
Felix Naumann, Ching-Tien Ho, et al.
Proceedings - International Conference on Data Engineering