David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Paper
On the ε-perturbation method for avoiding degeneracy
Abstract
Although it is NP-complete to decide whether a linear programming problem is degenerate, the ε-perturbation method can be used to reduce in polynomial time any linear programming problem with rational coefficients to a nondegenerate problem. The perturbed problem has the same status as the given one in terms of feasibility and unboundedness, and optimal bases of the perturbed problem are optimal in the given problem. © 1989.
Related
Simeon Furrer, Dirk Dahlhaus
ISIT 2005
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.