A note on degeneracy in linear programming

DOI10.1007/BF01580886MaRDI QIDQ3730338zbMATH OpenFDO

Authors Nimrod Megiddo

Publication date 1986

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01580886

zbMATH Keywords

degeneracyexiting a degenerate vertexrandomized simplexstrongly polynomial time

Mathematics Subject Classification ID

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

Recommendations

• Degeneracy: Resolve or Avoid?
• On degeneracy in linear programming and related problems
• Survey of solved and open problems in the degeneracy phenomenon
• Resolution of the problem of degeneracy in a primal and dual simplex algorithm
• scientific article; zbMATH DE number 3852781

Cites work

• A new polynomial-time algorithm for linear programming
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• New Finite Pivoting Rules for the Simplex Method
• On the average length of lexicographic paths

Cited in

(17)

• Removing degeneracy in LP-type problems revisited
• On the convexity of the multiplicative version of Karmarkar's potential function
• A new pivoting rule for solving various degeneracy problems
• Selected bibliography on degeneracy
• Degeneracy graphs: Theory and applications. An updated survey
• Learning in experimental games
• Degenerate optimal basis graphs in linear programming
• On the \(\epsilon\)-perturbation method for avoiding degeneracy
• An experimental study of constant-sum centipede games
• Men and progress in linear programming
• On the average length of lexicographic paths
• scientific article; zbMATH DE number 4114364 (Why is no real title available?)
• scientific article; zbMATH DE number 854120 (Why is no real title available?)
• Revisiting degeneracy, strict feasibility, stability, in linear programming
• Degeneracy resolution for bilinear utility functions
• On the number of degenerate simplex pivots
• On the number of degenerate simplex pivots

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3730338)