The Complexity and Approximability of Finding Maximum Feasible Subsystems of Linear Relations
The Complexity and Approximability of Finding Maximum Feasible Subsystems of Linear Relations
复制标题
DOI：
10.1016/0304-3975(94)00254-g
复制
发表时间：
1995-08
期刊：
影响因子：
--
通讯作者：
E. Amaldi;V. Kann
中科院分区：
文献类型：
--
作者：
E. Amaldi;V. Kann
我们研究组合问题，在给定线性关系系统的情况下，找到一个最大可行子系统，即满足尽可能多的关系的解决方案。这个名为 Max FLS 的一般问题的计算复杂性针对 =、⩾、> 和 ≠ 四种类型的关系进行了研究。还考虑了 Max FLS 的各种约束版本，其中必须满足关系子集或变量采用有界离散值。我们确定最佳解决这些问题的复杂性，并且每当它们难以解决时，我们就确定它们的近似程度。即使仅限于具有双极性系数的齐次系统，具有 =、⩾ 或 > 关系的最大 FLS 也是 NP 困难的，而对于具有实数系数的 ≠ 关系，它可以在多项式时间内求解。 Max FLS 的各种 NP-hard 版本属于不同的近似性类别，具体取决于关系的类型和附加约束。我们证明了近似性的范围从 Apx 完全问题（可以在一个常数内近似，但不能在每个常数内近似，除非 P = NP）到 NPO PB 完全问题（与具有多项式有界目标函数的所有 NP 优化问题一样难以近似）。虽然对于某些 ε > 0，具有方程和整数系数的 Max FLS 无法在 pε 内近似，其中 p 是关系数，但素数 q 的 GF(q) 上的相同问题可以在 q 内近似，但对于某些 ε > 0 则不能在 qε 内近似。具有严格或非严格不等式的最大 FLS 可以在 2 内近似，但不能在每个常数因子内近似。我们的结果还为 Max FLS 的两个变体的近似性提供了强有力的界限，其中 ⩾ 和 > 关系是在训练感知器（人工神经网络的构建块）以及设计线性分类器时出现的。
We study the combinatorial problem which consists, given a system of linear relations, of finding a maximum feasible subsystem, that is a solution satisfying as many relations as possible. The computational complexity of this general problem, named Max FLS, is investigated for the four types of relations =, ⩾, > and ≠. Various constrained versions of Max FLS, where a subset of relations must be satisfied or where the variables take bounded discrete values, are also considered. We establish the complexity of solving these problems optimally and, whenever they are intractable, we determine their degree of approximability. Max FLS with =, ⩾ or > relations is NP-hard even when restricted to homogeneous systems with bipolar coefficients, whereas it can be solved in polynomial time for ≠ relations with real coefficients. The various NP-hard versions of Max FLS belong to different approximability classes depending on the type of relations and the additional constraints. We show that the range of approximability stretches from Apx-complete problems which can be approximated within a constant but not within every constant unless P = NP, to NPO PB-complete ones that are as hard to approximate as all NP optimization problems with polynomially bounded objective functions. While Max FLS with equations and integer coefficients cannot be approximated within pεfor some ε > 0, where p is the number of relations, the same problem over GF(q) for a prime q can be approximated within q but not within qεfor some ε > 0. Max FLS with strict or nonstrict inequalities can be approximated within 2 but not within every constant factor. Our results also provide strong bounds on the approximability of two variants of Max FLS with ⩾ and > relations that arise when training perceptrons, which are the building blocks of artificial neural networks, and when designing linear classifiers.