Erratum: A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes

References

• Adler I. , Karp R. M. , Shamir R. A simplex variant solving an m × d linear program in O(min(m 2, d 2)) expected number of steps. J. Complexity (1987) 3 372 387 Crossref, Google Scholar
• Adler I. , Megiddo N. A simplex algorithm where the average number of steps is bounded between two quadratic functions of the smaller dimension. J. ACM (1985) 32 871 895 Crossref, Google Scholar
• Borgwardt K. H. Untersuchungen zur asymptotik der mittleren schrittzahl von simplexverfahren in der linearen optimierung (1977) . Dissertation, Universität Kaiserslautern Google Scholar
• Borgwardt K. H. Some distribution-independent results about the asymptotic order of the average number of pivot steps of the simplex method. Math. Oper. Res. (1982a) 7 441 462 Link, Google Scholar
• Borgwardt K. H. The average number of pivot steps required by the simplex-method is polynomial. Zeitschrift für Oper. Res. (1982b) 26 157 177 Crossref, Google Scholar
• Borgwardt K. H. The Simplex Method, A Probabilistic Analysis (1987) (Springer Verlag, Heidelberg) Crossref, Google Scholar
• Borgwardt K. H. , Damm R. , Donig R. , Joas G. Empirical studies on the average efficiency of simplex variants under rotation symmetry. ORSA J. Comput. (1993) 5 249 260 Link, Google Scholar
• Borgwardt K. H. , Schock E. Verschärfung des polynomialitätsbeweises für die erwartete anzahl von schattenecken im rotationssymmetrie-modell. Beiträge zur Angewandten Analysis und Informatik, Festschrift zu Ehren von Helmut Brakhage (1994a) (Shaker Verlag, Aachen) Google Scholar
• Borgwardt K. H. Improving the theoretical upper bound for the expected number of shadow-vertices in the Rotation-Symmetry-Model. (1994b) . Schwerpunktreport der Deutschen Forschungsgemeinschaft Nr. 537, Universität Augsburg Google Scholar
• Haimovich M. The simplex algorithm is Very Good!—On the expected number of pivot steps and related properties of random linear programs. (1983) (Columbia University, New York) . Report Google Scholar
• Höfner G. Lineare optimierung mit dem schatteneckenalgorithmus—Untersuchungen zum mittleren rechenaufwand und entartungsverhalten (1995) (Dissertation, Universität Augsburg) Google Scholar
• Huhn P. Schranken für die durchschnittliche laufzeit von simplexverfahren und innere-punkl-verfahren (1997) (Dissertation, Universität Augsburg) Google Scholar
• Küfer K. On the variance of the number of pivot steps required by the simplex algorithm. Math. Methods Oper. Res. (1995) 42 1 24 Crossref, Google Scholar
• Küfer K. An improved asymptotic analysis of the number of pivot steps required by the simplex algorithm. Math. Methods Oper. Res. (1996) 44 147 170 Crossref, Google Scholar
• Shamir R. The efficiency of the simplex method. Management Sci. (1987) 33 301 334 Link, Google Scholar
• Smale S. On the average speed of the simplex method of linear programming. Math. Programming (1983) 27 241 262 Crossref, Google Scholar
• Todd M. J. Polynomial expected behavior of a pivoting algorithm for linear complimentarity and linear programming problems. Math. Programming (1986) 35 173 192 Crossref, Google Scholar