On the ffl-perturbation method for avoiding degeneracy tech. report
| Author(s) : | R. Chandrasekaran Nimrod Megiddo, |
| Publisher : | N/A |
| Publication Date : | 1988 |
| ISSN : | N/A |
| Abstract : | Abstract. Although it is NP-complete to decide whether a linear programming problemis degenerate, the ffl-perturbation method can be used to reduce in polynomial time any linear programming problemwith 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., |