An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm

  • Let \(a_1,\dots,a_m\) be i.i .d. vectors uniform on the unit sphere in \(\mathbb{R}^n\), \(m\ge n\ge3\) and let \(X\):= {\(x \in \mathbb{R}^n \mid a ^T_i x\leq 1\)} be the random polyhedron generated by. Furthermore, for linearly independent vectors \(u\), \(\bar u\) in \(\mathbb{R}^n\), let \(S_{u, \bar u}(X)\) be the number of shadow vertices of \(X\) in \(span (u, \bar u\)). The paper provides an asymptotic expansion of the expectation value \(E (S_{u, \bar u})\) for fixed \(n\) and \(m\to\infty\). The first terms of the expansion are given explicitly. Our investigation of \(E (S_{u, \bar u})\) is closely connected to Borgwardt's probabilistic analysis of the shadow vertex algorithm - a parametric variant of the simplex algorithm. We obtain an improved asymptotic upper bound for the number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.
Verfasserangaben:Karl-Heinz Küfer
URN (Permalink):urn:nbn:de:hbz:386-kluedo-50490
Schriftenreihe (Bandnummer):Preprints (rote Reihe) des Fachbereich Mathematik (262)
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):08.11.2017
Jahr der Veröffentlichung:1995
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):08.11.2017
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)

$Rev: 13581 $