On the complexity of solving feasible systems of linear inequalities specified with approximate data |
| |
Authors: | Sharon Filipowski |
| |
Institution: | (1) Department of Industrial and Manufacturing Systems Engineering, Iowa State University, 205 Engineering Annex, 50011 Ames, IA, United States |
| |
Abstract: | 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. |
| |
Keywords: | Complexity of linear programming Approximate data Approximate solutions Condition measures Knowledge |
本文献已被 SpringerLink 等数据库收录! |