TY - RPRT
A1 - Küfer, Karl-Heinz
T1 - An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm
N2 - 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.
T3 - Preprints (rote Reihe) des Fachbereich Mathematik - 262
Y1 - 1995
UR - https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5049
UR - https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-50490
ER -