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.