1982 Reports

# Complexity of Linear Programming

The complexity of linear programming is discussed in the "integer" and "real number" models of computation. Even though the integer model is widely used in theoretical computer science, the real number model is more useful for estimating an algorithm's running time in actual computation. Although the ellipsoid algorithm is a polynomial-time algorithm in the integer model, we prove that it has unbounded complexity in the real number model. We conjecture that there exists no polynomial-time algorithm for the linear inequalities problem in the real number model. We also conjecture that linear inequalities are strictly harder than linear equalities in all "reasonable" models of computation.

## Subjects

## Files

- cucs-027-82.pdf application/pdf 225 KB Download File

## More About This Work

- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-027-82
- Published Here
- October 25, 2011