Some NP-complete problems in linear programming
Operations Research LettersPublished 1 July 1982
R. Chandrasekaran, Santosh N. Kabadi, Katta G. Murthy
Citations44
SJR quartileQ2
SJR score0.44
SNIP0.68
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Degeneracy checking in linear programming is NP-complete, so is the problem of checking whether there exists a basic feasible solution with a specified objective value.
Abstract
Degeneracy checking in linear programming is NP-complete. So is the problem of checking whether there exists a basic feasible solution with a specified objective value.
Keywords
Computer ScienceMathematicsEngineering
Reducibility among Combinatorial Problems
10,823 Citations1972Richard M. Karp
Naval Research Logistics QuarterlyCycling in the dual simplex algorithm
138 Citations1955E. M. L. Beale
Naval Research Logistics QuarterlyA note on cycling in the simplex method
69 Citations1969K. T. Marshall, J. W. Suurballe
Mathematical ProgrammingCycling in linear complementarity problems
23 Citations1979Michael M. Kostreva
A bound for the minimum length of a cycle in Lemke's Algorithm is derived and it is illustrated that this bound is sharp, and that the fewest number of variables is seven.
Naval Research Logistics QuarterlyCycling in the transportation problem
20 Citations1964Betty Jane Gassner