Some NP-complete problems in linear programming

DOI10.1016/0167-6377(82)90006-2zbMath0506.90052OpenAlexW2087904554MaRDI QIDQ1837108

Katta G. Murty, R. Chandrasekaran, Santosh N. Kabadi

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0167-6377(82)90006-2

zbMATH Keywords

NP-complete problemslinear dependencesubset sum problemdegeneracy testingequal partial sums problemexistence of basic feasible solutions with specified values

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items

Matchings in colored bipartite networks ⋮ Degeneracy in transportation problems ⋮ Mathematical systems for enhancing diffuse images of point sources ⋮ Revisiting degeneracy, strict feasibility, stability, in linear programming ⋮ Eigenpolytope Universality and Graphical Designs ⋮ Nonlinear bipartite matching ⋮ Sign-solvable linear complementarity problems ⋮ Bicolored matchings in some classes of graphs ⋮ Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. ⋮ Adjacency on the constrained assignment problem ⋮ On the \(\epsilon\)-perturbation method for avoiding degeneracy ⋮ Combinatoric classes of the transportation problem and their properties

Cites Work

• The Transhipment Problem
• Cycling in linear complementarity problems
• A Technique for Resolving Degeneracy in Linear Programming
• Cycling in the transportation problem
• A note on cycling in the simplex method
• Optimality and Degeneracy in Linear Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item