Minimum relevant variables in linear system
The Min-RVLS problem (MINimum Relevant Variables in Linear System) 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.
Definition
A Min-RVLS problem is defined by:[1]
- A binary relation R, which is one of {=, ≥, >, ≠};
- An m-by-n matrix A (where m is the number of constraints and n the number of variables);
- An m-by-1 vector b.
The linear system is given by: A x R b. 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.
Special case
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.
References
- ^ "On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems". Theoretical Computer Science. 209 (1–2): 237–260. 1998-12-06. doi:10.1016/S0304-3975(97)00115-1. ISSN 0304-3975.
- ^ Johnson, David S.; Garey, M. R. (1979). "Computers and Intractability: A Guide to the Theory of NP-Completeness". www.semanticscholar.org. Retrieved 2019-01-07.