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

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

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.