ISSN:
1432-5217
Schlagwort(e):
Linear programming
;
simplex algorithm
;
probabilistic analysis
;
asymptotic expansion
;
convex hull
;
stochastic geometry
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
,
Wirtschaftswissenschaften
Notizen:
Abstract Leta 1 ...,a m be i.i.d. points uniformly on the unit sphere in ℝ n ,m ≥n ≥ 3, and letX:= {xε ℝ n |a i T x≤1} be the random polyhedron generated bya 1, ...,a m . Furthermore, for linearly independent vectorsu, ū in ℝ n , letS u ,ū (X) be the number of shadow vertices ofX inspan(u,ū). The paper provides an asymptotic expansion of the expectation value¯S n,m := in4 1 E(S u,ū ) for fixedn andm→ ∞.¯S n,m equals the expected number of pivot steps that the shadow vertex algorithm — a parametric variant of the simplex algorithm — requires in order to solve linear programming problems of type max u T ,xεX, if the algorithm will be started with anX-vertex solving the problem max ū T ,x ε X. Our analysis is closely related to Borgwardt's probabilistic analysis of the simplex algorithm. We obtain a refined asymptotic analysis of the expected number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01194327
Permalink
