On the \(\epsilon\)-perturbation method for avoiding degeneracy

DOI10.1016/0167-6377(89)90014-XzbMath0682.90057MaRDI QIDQ1824546

Nimrod Megiddo, R. Chandrasekaran

Publication date: 1989

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

degeneracyNP-completepolynomial time\(\epsilon\)-perturbation method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items (9)

Computing maximum mean cuts ⋮ From Parity and Payoff Games to Linear Programming ⋮ Recovery-to-optimality: a new two-stage approach to robustness with an application to aperiodic timetabling ⋮ \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma ⋮ Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks ⋮ A class of primal affine scaling algorithms ⋮ Colorful linear programming, Nash equilibrium, and pivots ⋮ Computing solutions of the multiclass network equilibrium problem with affine cost functions ⋮ Concurrent estimation of efficiency, effectiveness and returns to scale

Cites Work

• Unnamed Item
• Some NP-complete problems in linear programming
• Optimality and Degeneracy in Linear Programming

This page was built for publication: On the \(\epsilon\)-perturbation method for avoiding degeneracy