The complexity of linear programming

David P. Dobkin; Steven P. Reiss

doi:10.1016/0304-3975(80)90031-6

The complexity of linear programming

David P. Dobkin, Steven P. Reiss

Research output: Contribution to journal › Article › peer-review

32 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 language	English (US)
Pages (from-to)	1-18
Number of pages	18
Journal	Theoretical Computer Science
Volume	11
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(80)90031-6
State	Published - May 1980

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/0304-3975(80)90031-6

Cite this

@article{2ae4b0e2e9e948a1a7d635626716db14,

title = "The complexity of linear programming",

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.",

author = "Dobkin, {David P.} and Reiss, {Steven P.}",

note = "Funding Information: * Portions of this research were supported by an NSF Graduate Fellowship, NSF Grant MCS76-11460 and ONR Grant NO0014-75-C-0450. Most of this work was dcne when both authors were at Yale.",

year = "1980",

month = may,

doi = "10.1016/0304-3975(80)90031-6",

language = "English (US)",

volume = "11",

pages = "1--18",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - The complexity of linear programming

AU - Dobkin, David P.

AU - Reiss, Steven P.

N1 - Funding Information: * Portions of this research were supported by an NSF Graduate Fellowship, NSF Grant MCS76-11460 and ONR Grant NO0014-75-C-0450. Most of this work was dcne when both authors were at Yale.

PY - 1980/5

Y1 - 1980/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=11544334931&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=11544334931&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(80)90031-6

DO - 10.1016/0304-3975(80)90031-6

M3 - Article

AN - SCOPUS:11544334931

SN - 0304-3975

VL - 11

SP - 1

EP - 18

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -

The complexity of linear programming

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this