On the Complexity of Solving Sparse Symmetric Linear Programs Specified with Approximate Data

An algorithm that solves symmetric linear programs specified with approximate data is given. The algorithm uses knowledge that several of the constraint matrix coefficients of the actual (unknown) instance are equal to zero to reduce the data precision necessary to solve the instance in question. The algorithm is computationally efficient and requires not much more data accuracy than the minimum amount necessary to solve the actual instance. This work aids in the development of a computational complexity theory that uses approximate data and knowledge.