On the complexity of solving feasible systems of linear inequalities specified with approximate data

An algorithm that gives an approximate solution of a desired accuracy to a system of linear inequalities specified with approximate data is presented. It uses knowledge that the actual instance is feasible to reduce the data precision necessary to give an approximate solution to the actual instance. In some cases, this additional information allows problem instances that are ill-posed without the knowledge of feasibility to be solved. The algorithm is computationally efficient and requires not much more data accuracy than the minimal amount necessary to give an approximate solution of the desired accuracy. This work aids in the development of a computational complexity theory that uses approximate data and knowledge.