Abstract
A bound for the minimum length of a cycle in Lemke's Algorithm is derived. An example illustrates that this bound is sharp, and that the fewest number of variables is seven.
This is a preview of subscription content, log in via an institution to check access.
References
E.M.L. Beale, “Cycling in the dual simplex algorithm”,Naval Research Logistics Quarterly 2 (1955) 269–275.
G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, 1963).
A.J. Hoffman, “Cycling in the simplex algorithm”, National Bureau of Standards, Rept. No. 2974 (December 1953).
C.E. Lemke, “Bimatrix equilibrium points and mathematical programming”,Management Science 11 (1965) 681–689.
C.M. Lemke, “On complementary pivot theory”, in: G.B. Dantzig and A.F. Veinott, Jr., eds.,Mathematics of the Decision Sciences (Am. Math. Soc., Providence, RI, 1968) pp. 95–114.
A. Ravindran, “Algorithm 431 [H]. A computer routine for quadratic and linear programming problems”,Communications of the ACM 15 (1972) 818–820.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kostreva, M.M. Cycling in linear complementarity problems. Mathematical Programming 16, 127–130 (1979). https://doi.org/10.1007/BF01582098
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582098