The complexity and approximability of finding maximum feasible subsystems of linear relations

AbstractWe 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