## 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 (permanent link): | urn:nbn:de:hbz:386-kluedo-50490 |

Serie (Series number): | Preprints (rote Reihe) des Fachbereich Mathematik (262) |

Document Type: | Report |

Language of publication: | English |

Publication Date: | 2017/11/08 |

Year of Publication: | 1995 |

Publishing Institute: | Technische Universität Kaiserslautern |

Date of the Publication (Server): | 2017/11/08 |

Number of page: | 16 |

Faculties / Organisational entities: | 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) |