Academic Journal
Two new bounds for the random-edge simplex algorithm
| العنوان: | Two new bounds for the random-edge simplex algorithm |
|---|---|
| المؤلفون: | Bernd Gärtner, Volker Kaibel |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://arxiv.org/pdf/math/0502025v2.pdf. |
| سنة النشر: | 2008 |
| المجموعة: | CiteSeerX |
| الوصف: | We prove that the Random-Edge simplex algorithm requires an expected number of at most 13n / √ d pivot steps on any simple d-polytope with n vertices. This is the first nontrivial upper bound for general polytopes. We also describe a refined analysis that potentially yields much better bounds for specific classes of polytopes. As one application, we show that for combinatorial d-cubes, the trivial upper bound of 2 d on the performance of Random-Edge can asymptotically be improved by any desired polynomial factor in d. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.236.6852; http://arxiv.org/pdf/math/0502025v2.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.236.6852 http://arxiv.org/pdf/math/0502025v2.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.B2D18D16 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |