Complexity of linear programming |
| |
Authors: | JF Traub H Woźniakowski |
| |
Institution: | 1. Institute of Informatics, University of Warsaw, Warsaw, Poland;2. Department of Computer Science, Columbia University, New York, NY 10027, U.S.A. |
| |
Abstract: | 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. |
| |
Keywords: | Computational complexity models of computation ellipsoid algorithm linear programming linear inequalities polynomial-time algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|