The complexity of linear programming

David P. Dobkin, Steven P. Reiss

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


The complexity of linear programming and other problems in the geometry of d-dimensions is studied. A notion of LP-completeness is introduced, and a set of problems is shown to be (polynomially) equivalent to linear programming. Many of these problems involve computation of subsets of convex hulls of polytopes, and require O(n log n) operations for d=2. Known results are surveyed in order to give an interesting characterization for the complexity of linear programming and a transformation is given to produce NP-complete versions of LP-complete provlems.

Original languageEnglish (US)
Pages (from-to)1-18
Number of pages18
JournalTheoretical Computer Science
Issue number1
StatePublished - May 1980

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The complexity of linear programming'. Together they form a unique fingerprint.

Cite this