ON THE APPROXIMABILITY OF MINIMIZING NONZERO VARIABLES OR UNSATISFIEDRELATIONS IN LINEAR-SYSTEMS

We investigate the computational complexity of two closely related cla sses of combinatorial optimization problems for linear systems which a rise in various fields such as machine learning, operations research a nd pattern recognition. In the first class (MIN ULR) one wishes, given a possibly infeasible system of linear relations, to find a solution that violates as few relations as possible while satisfying all the ot hers. In the second class (MIN RVLS) the linear system is supposed to be feasible and one looks for a solution with as few nonzero variables as possible. For both MIN ULR and MIN RVLS the four basic types of re lational operators =, greater than or equal to, > and not equal are co nsidered. While MIN RVLS with equations was mentioned to be NP-hard in (Garey and Johnson, 1979), we established in (Amaldi; 1992; Amaldi an d Kann, 1995) that MIN ULR with equalities and inequalities are NP-har d even when restricted to homogeneous systems with bipolar coefficient s. The latter problems have been shown hard to approximate in (Arora e t al., 1993). In this paper we determine strong bounds on the approxim ability of various variants of MIN RVLS and MIN ULR, including constra ined ones where the variables are restricted to take binary values or where some relations are mandatory while others are optional. The vari ous NP-hard versions turn out to have different approximability proper ties depending on the type of relations and the additional constraints , but none of them can be approximated within any constant factor, unl ess P = NP. Particular attention is devoted to two interesting special cases that occur in discriminant analysis and machine learning. In pa rticular, we disprove a conjecture of van Horn and Martinet (1992) reg arding the existence of a polynomial-time algorithm to design linear c lassifiers (or perceptrons) that involve a close-to-minimum number of features. (C) 1998 Published by Elsevier Science B.V. All rights reser ved.