期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
