An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm
Identifieur interne : 001C83 ( Main/Exploration ); précédent : 001C82; suivant : 001C84An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm
Auteurs : Karl Heinz Küfer [Allemagne]Source :
- Mathematical Methods of Operations Research [ 1432-2994 ] ; 1996-06-01.
English descriptors
- KwdEn :
- Teeft :
- Algorithm, Asymptotic, Asymptotic analysis, Asymptotic behaviour, Asymptotic expansion, Asymptotic expansions, Average number, Borgwardt, Coefficient, Density function, Expectation value, Facet, Hyperplane, Independent vectors, Linear programming problems, Matrix, Mittleren schrittzahl, Operations research, Other hand, Pivot, Pivot steps, Polar polytope, Positive constants, Probabilistic analysis, Series representation, Shadow vertex, Shadow vertex algorithm, Shadow vertices, Simplex, Simplex algorithm, Simplex method, Spherical angle, Spherical angles, Spherical parts, Spherical symmetry, Spherically, Stochastic geometry, Surface integral, Taylor series, Transformation formula, Uniform distribution, Unit ball, Unit sphere.
Abstract
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.
Url:
DOI: 10.1007/BF01194327
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000C57
- to stream Istex, to step Curation: 000C57
- to stream Istex, to step Checkpoint: 000A62
- to stream Main, to step Merge: 001D51
- to stream Main, to step Curation: 001C83
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm</title><author><name sortKey="Kufer, Karl Heinz" sort="Kufer, Karl Heinz" uniqKey="Kufer K" first="Karl Heinz" last="Küfer">Karl Heinz Küfer</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:D810AE5FE13FD52CDA1E1F134E6798A7950BEC29</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1007/BF01194327</idno><idno type="url">https://api.istex.fr/ark:/67375/1BB-CHD7V0WB-J/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000C57</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000C57</idno><idno type="wicri:Area/Istex/Curation">000C57</idno><idno type="wicri:Area/Istex/Checkpoint">000A62</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000A62</idno><idno type="wicri:doubleKey">1432-2994:1996:Kufer K:an:improved:asymptotic</idno><idno type="wicri:Area/Main/Merge">001D51</idno><idno type="wicri:Area/Main/Curation">001C83</idno><idno type="wicri:Area/Main/Exploration">001C83</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm</title><author><name sortKey="Kufer, Karl Heinz" sort="Kufer, Karl Heinz" uniqKey="Kufer K" first="Karl Heinz" last="Küfer">Karl Heinz Küfer</name><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Dept. of Mathematics, University of Kaiserslautern, Erwin-Schrödinger-Str., 67663, Kaiserslautern</wicri:regionArea><placeName><region type="land" nuts="2">Rhénanie-Palatinat</region><settlement type="city">Kaiserslautern</settlement></placeName><orgName type="university">Université technique de Kaiserslautern</orgName></affiliation></author></analytic><monogr></monogr><series><title level="j">Mathematical Methods of Operations Research</title><title level="j" type="abbrev">Mathematical Methods of Operations Research</title><idno type="ISSN">1432-2994</idno><idno type="eISSN">1432-5217</idno><imprint><publisher>Physica-Verlag</publisher><pubPlace>Heidelberg</pubPlace><date type="published" when="1996-06-01">1996-06-01</date><biblScope unit="volume">44</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="147">147</biblScope><biblScope unit="page" to="170">170</biblScope></imprint><idno type="ISSN">1432-2994</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">1432-2994</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Linear programming</term><term>asymptotic expansion</term><term>convex hull</term><term>probabilistic analysis</term><term>simplex algorithm</term><term>stochastic geometry</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term><term>Asymptotic</term><term>Asymptotic analysis</term><term>Asymptotic behaviour</term><term>Asymptotic expansion</term><term>Asymptotic expansions</term><term>Average number</term><term>Borgwardt</term><term>Coefficient</term><term>Density function</term><term>Expectation value</term><term>Facet</term><term>Hyperplane</term><term>Independent vectors</term><term>Linear programming problems</term><term>Matrix</term><term>Mittleren schrittzahl</term><term>Operations research</term><term>Other hand</term><term>Pivot</term><term>Pivot steps</term><term>Polar polytope</term><term>Positive constants</term><term>Probabilistic analysis</term><term>Series representation</term><term>Shadow vertex</term><term>Shadow vertex algorithm</term><term>Shadow vertices</term><term>Simplex</term><term>Simplex algorithm</term><term>Simplex method</term><term>Spherical angle</term><term>Spherical angles</term><term>Spherical parts</term><term>Spherical symmetry</term><term>Spherically</term><term>Stochastic geometry</term><term>Surface integral</term><term>Taylor series</term><term>Transformation formula</term><term>Uniform distribution</term><term>Unit ball</term><term>Unit sphere</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Kaiserslautern</li></settlement><orgName><li>Université technique de Kaiserslautern</li></orgName></list><tree><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Kufer, Karl Heinz" sort="Kufer, Karl Heinz" uniqKey="Kufer K" first="Karl Heinz" last="Küfer">Karl Heinz Küfer</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/H2N2V1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001C83 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001C83 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= H2N2V1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:D810AE5FE13FD52CDA1E1F134E6798A7950BEC29
|texte= An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm
}}
| This area was generated with Dilib version V0.6.33. |  |