Research Planning Grant: Approximation Algorithms for Sparse Optimization Problems with Inaccurate Data

小行星9409215 本研究的目的是构造线性规划算法，提供近似的解决方案时，使用不精确的数据。 该算法将通过假设某些系数为零值来启动求解过程，以便降低解决问题实例所需的数据准确度。 该算法将实施，测试，并与基于区间分析的算法的性能进行比较。 从这项研究中获得的结果将被用来开发新的计算复杂性理论，包括使用不精确的数据在解决线性规划问题。 理解解决问题实例的复杂性，只给出要解决的实例数据的近似值，将导致算法的开发，可以更有效地解决各种各样的工程问题。

9409215 Filipowski This research is aimed at constructing linear programming algorithms that provide approximate solutions when inexact data is used. The algorithms will initiate the solution process by assuming zero values for some coefficients so as to lessen the degree of data accuracy required to solve a problem instance. The algorithms will be implemented, tested, and compared with the performance of interval analysis based algorithms. The results obtained from this research will be used to develop new computational complexity theory that incorporates the use of inexact data in solving linear programming problems. Understanding the complexity of solving problem instances given only an approximation to the data of the instance to be solved will lead to the development of algorithms that can solve more efficiently, a wide variety of engineering problems.