Minimum relevant variables in linear system (Min-RVLS) is a problem in mathematical optimization. Given a linear program, it is required to find a feasible solution in which the number of non-zero variables is as small as possible.
The problem is known to be NP-hard and even hard to approximate.
A Min-RVLS problem is defined by: [1]
The linear system is given by: A x R b. It is assumed to be feasible (i.e., satisfied by at least one x). Depending on R, there are four different variants of this system: A x = b, A x ≥ b, A x > b, A x ≠ b.
The goal is to find an n-by-1 vector x that satisfies the system A x R b, and subject to that, contains as few as possible nonzero elements.
The problem Min-RVLS[=] was presented by Garey and Johnson, [2] who called it "minimum weight solution to linear equations". They proved it was NP-hard, but did not consider approximations.
The Min-RVLS problem is important in machine learning and linear discriminant analysis. Given a set of positive and negative examples, it is required to minimize the number of features that are required to correctly classify them. [3] The problem is known as the minimum feature set problem. An algorithm that approximates Min-RVLS within a factor of could substantially reduce the number of training samples required to attain a given accuracy level. [4]
The shortest codeword problem in coding theory is the same problem as Min-RVLS[=] when the coefficients are in GF(2).
In minimum unsatisfied linear relations (Min-ULR), we are given a binary relation R and a linear system A x R b, which is now assumed to be infeasible. The goal is to find a vector x that violates as few relations as possible, while satisfying all the others.
Min-ULR[≠] is trivially solvable, since any system with real variables and a finite number of inequality constraints is feasible. As for the other three variants:
In the complementary problem maximum feasible linear subsystem (Max-FLS), the goal is to find a maximum subset of the constraints that can be satisfied simultaneously. [5]
All four variants of Min-RVLS are hard to approximate. In particular all four variants cannot be approximated within a factor of , for any , unless NP is contained in DTIME(). [1]: 247–250 The hardness is proved by reductions:
On the other hand, there is a reduction from Min-RVLS[=] to Min-ULR[=]. It also applies to Min-ULR[≥] and Min-ULR[>], since each equation can be replaced by two complementary inequalities.
Therefore, when R is in {=,>,≥}, Min-ULR and Min-RVLS are equivalent in terms of approximation hardness.
Minimum relevant variables in linear system (Min-RVLS) is a problem in mathematical optimization. Given a linear program, it is required to find a feasible solution in which the number of non-zero variables is as small as possible.
The problem is known to be NP-hard and even hard to approximate.
A Min-RVLS problem is defined by: [1]
The linear system is given by: A x R b. It is assumed to be feasible (i.e., satisfied by at least one x). Depending on R, there are four different variants of this system: A x = b, A x ≥ b, A x > b, A x ≠ b.
The goal is to find an n-by-1 vector x that satisfies the system A x R b, and subject to that, contains as few as possible nonzero elements.
The problem Min-RVLS[=] was presented by Garey and Johnson, [2] who called it "minimum weight solution to linear equations". They proved it was NP-hard, but did not consider approximations.
The Min-RVLS problem is important in machine learning and linear discriminant analysis. Given a set of positive and negative examples, it is required to minimize the number of features that are required to correctly classify them. [3] The problem is known as the minimum feature set problem. An algorithm that approximates Min-RVLS within a factor of could substantially reduce the number of training samples required to attain a given accuracy level. [4]
The shortest codeword problem in coding theory is the same problem as Min-RVLS[=] when the coefficients are in GF(2).
In minimum unsatisfied linear relations (Min-ULR), we are given a binary relation R and a linear system A x R b, which is now assumed to be infeasible. The goal is to find a vector x that violates as few relations as possible, while satisfying all the others.
Min-ULR[≠] is trivially solvable, since any system with real variables and a finite number of inequality constraints is feasible. As for the other three variants:
In the complementary problem maximum feasible linear subsystem (Max-FLS), the goal is to find a maximum subset of the constraints that can be satisfied simultaneously. [5]
All four variants of Min-RVLS are hard to approximate. In particular all four variants cannot be approximated within a factor of , for any , unless NP is contained in DTIME(). [1]: 247–250 The hardness is proved by reductions:
On the other hand, there is a reduction from Min-RVLS[=] to Min-ULR[=]. It also applies to Min-ULR[≥] and Min-ULR[>], since each equation can be replaced by two complementary inequalities.
Therefore, when R is in {=,>,≥}, Min-ULR and Min-RVLS are equivalent in terms of approximation hardness.