 |
|
||||||||||
Towards a Unified Framework for Randomized Pivoting Algorithms in Linear Programming
L. Finschi and K. Fukuda and H.-J. Lüthi
1998 September 10
Appeared in: Operations Research Proceedings 1998 (Zurich), Springer, Berlin, pp. 113-122 (1999)
Abstract
We study linear programming (LP) algorithms. Of particular interest are bounds for the number of elementary arithmetic operations necessary to solve a linear program. The best bounds that depend only on the sizes of a basis and a nonbasis have been found for a family of randomized pivoting algorithms. However, the original descriptions and analyses of these algorithms use several different geometric and abstract settings. In this paper we present a unified framework in which we describe two known algorithms as special simplex methods and analyse their complexities and differences.
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
