The complexity of linear programming

David P. Dobkin, Steven P. Reiss

Research output: Contribution to journalArticle

24 Scopus citations

Abstract

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
Volume11
Issue number1
DOIs
StatePublished - May 1980
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this