Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs
Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs
复制标题
判定线性规划解存在性的不适定性和复杂性
DOI：
--
复制
发表时间：
1996
影响因子：
3.1
通讯作者：
Jorge R. Vera
中科院分区：
文献类型：
--
作者：
Jorge R. Vera
本文讨论用近似数据确定线性规划解的存在性的有效算法。这在只有问题的真实的数据的近似值可用于计算的应用中是重要的，或者在舍入误差阻止使用精确数字的应用中是重要的。该算法是有效的，从计算和所需的数据的角度来看，需要过多的计算和过于精确的近似，只有近不适定的情况下。我们说明了如何接近不适定性措施的“条件”的问题，并在复杂性分析中发挥了重要作用。这项工作是一个步骤，了解不适定性的优化问题和发展的一般复杂性理论的问题解决近似数据。
We discuss efficient algorithms for deciding existence of solutions to linear programs specified with approximate data. This is important in applications where only an approximation to the real data of the problem is available for computation, or where rounding errors prevent the use of exact numbers. The algorithms are efficient from the point of view of computation and needed data, requiring excessive computation and an excessively precise approximation only for nearly ill-posed instances. We illustrate how the proximity to ill-posedness measures the “conditioning” of the problem and plays an important role in the complexity analysis. This work is one step toward the understanding of ill-posedness in optimization problems and the development of a general complexity theory of problem solving with approximate data.