A note on degeneracy in linear programming

DOI10.1007/BF01580886zbMath0596.90057MaRDI QIDQ3730338

Nimrod Megiddo

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

degeneracystrongly polynomial timeexiting a degenerate vertexrandomized simplex

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Methods of successive quadratic programming type (90C55)

Related Items (9)

Learning in experimental games ⋮ On the average length of lexicographic paths ⋮ On the convexity of the multiplicative version of Karmarkar's potential function ⋮ Revisiting degeneracy, strict feasibility, stability, in linear programming ⋮ A new pivoting rule for solving various degeneracy problems ⋮ Men and progress in linear programming ⋮ An experimental study of constant-sum centipede games ⋮ Selected bibliography on degeneracy ⋮ Degeneracy graphs: Theory and applications. An updated survey

Cites Work

• A new polynomial-time algorithm for linear programming
• On the average length of lexicographic paths
• New Finite Pivoting Rules for the Simplex Method
• Unnamed Item

This page was built for publication: A note on degeneracy in linear programming