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.
Author: | Karl-Heinz Küfer |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-50490 |
Series (Serial Number): | Preprints (rote Reihe) des Fachbereich Mathematik (262) |
Document Type: | Report |
Language of publication: | English |
Date of Publication (online): | 2017/11/08 |
Year of first Publication: | 1995 |
Publishing Institution: | Technische Universität Kaiserslautern |
Date of the Publication (Server): | 2017/11/08 |
Page Number: | 16 |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Mathematik |
DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Licence (German): | Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0) |