ISSN:
1436-4646
Keywords:
Degeneracy
;
strongly polynomial time
;
randomized simplex
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We show that the problem of exiting a degenerate vertex is as hard as the general linear programming problem. More precisely, every linear programming problem can easily be reduced to one where the second best vertex (which is highly degenerate) is already given. So, to solve the latter, it is sufficient to exit that vertex in a direction that improves the objective function value.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01580886
Permalink