The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes
| dc.creator | Gillmann, Rafael | |
| dc.date | 2006-05-04 | |
| dc.date.accessioned | 2026-07-07T07:13:54Z | |
| dc.date.available | 2026-07-07T07:13:54Z | |
| dc.description | The simplex algorithm using the random edge pivot-rule on any realization of a dual cyclic 4-polytope with n facets does not take more than O(n) pivot-steps. This even holds for general abstract objective functions (AOF) / acyclic unique sink orientations (AUSO). The methods can be used to show analogous results for products of two polygons. In contrast, we show that the random facet pivot-rule is slow on dual cyclic 4-polytopes, i.e. there are AUSOs on which random facet takes at least Ω(n^2) steps. | |
| dc.description | 31 Pages, 11 figures | |
| dc.identifier | https://arxiv.org/abs/math/0605117 | |
| dc.identifier | http://arxiv.org/abs/math/0605117 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/112656 | |
| dc.subject | Combinatorics | |
| dc.subject | Optimization and Control | |
| dc.subject | 90C05 (Primary); 52B12, 68W20 (Secondary) | |
| dc.title | The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes | |
| dc.type | text |