LEMKE PATHS ON SIMPLE POLYTOPES

Authors
MORRIS WD
Citation
Wd. Morris, LEMKE PATHS ON SIMPLE POLYTOPES, Mathematics of operations research, 19(4), 1994, pp. 780-789
Citations number
16
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics
Journal title
Mathematics of operations research → ACNP
ISSN journal
0364765X
Volume
19
Issue
4
Year of publication
1994
Pages
780 - 789
Database
ISI
SICI code
0364-765X(1994)19:4<780:LPOSP>2.0.ZU;2-D
Abstract
Lemke paths are often used in the solution of nonlinear programming pr oblems. We investigate a number of properties of Lemke paths, motivate d by the d-step conjecture for linear programming. Some negative resul ts are presented, including families of Lemke paths, for which the len gth of the shortest grows exponentially, joining pairs of vertices of a sequence of polytopes.