A note on degeneracy in linear programming |
| |
Authors: | Nimrod Megiddo |
| |
Affiliation: | (1) The IBM Almaden Research Center, 650 Harry Road, 95120-6099 San Jose, CA, USA;(2) Department of Statistics, Tel Aviv University, Tel Aviv, Israel |
| |
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. |
| |
Keywords: | Degeneracy strongly polynomial time randomized simplex |
本文献已被 SpringerLink 等数据库收录! |
|