### 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 | |

State | Published - May 1980 |

Externally published | Yes |

### 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

Dobkin, D. P., & Reiss, S. P. (1980). The complexity of linear programming.

*Theoretical Computer Science*,*11*(1), 1-18. https://doi.org/10.1016/0304-3975(80)90031-6