TR96-015 Authors: Edoardo Amaldi, Viggo Kann

Publication: 16th February 1996 22:43

Downloads: 2171

Keywords:

We investigate the computational complexity of two classes of

combinatorial optimization problems related to linear systems

and study the relationship between their approximability properties.

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 others. 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 relational

operators =, >=, > and \= are considered. While MIN RVLS with

equations was known to be NP-hard in (Garey and Johnson 79), we

established in (Amaldi 92, Amaldi and Kann 95) that MIN ULR with

equalities and inequalities are NP-hard even when restricted to

homogeneous systems with bipolar coefficients. The latter problems

have been shown hard to approximate in (Arora et al. 93).

In this paper we determine strong bounds on the approximability of

various variants of MIN RVLS and MIN ULR, including constrained ones

where the variables are restricted to take bounded discrete values or

where some relations are mandatory while others are optional.

The various NP-hard versions turn out to have different approximability

properties depending on the type of relations and the additional

constraints, but none of them can be approximated within any constant

factor, unless P=NP.

Two interesting special cases of MIN RVLS and MIN ULR that arise in

discriminant analysis and machine learning are also discussed.

In particular, we disprove a conjecture regarding the existence of a

polynomial time algorithm to design linear classifiers (or perceptrons)

that use a close-to-minimum number of features.