Minimum relevant variables in linear system: Difference between revisions

Revision as of 08:26, 7 January 2019

Revision as of 08:33, 7 January 2019

Line 1:

The '''Min-RVLS''' problem<ref>{{Cite journal|date=1998-12-06|title=On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems|url=https://www.sciencedirect.com/science/article/pii/S0304397597001151|journal=Theoretical Computer Science|language=en|volume=209|issue=1-2|pages=237–260|doi=10.1016/S0304-3975(97)00115-1|issn=0304-3975}}</ref> (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-hardness|NP-hard]] and even hard to approximate.

== Definition ==

<br />

A Min-RVLS problemis defined by:<ref>{{Cite journal|date=1998-12-06|title=On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems|url=https://www.sciencedirect.com/science/article/pii/S0304397597001151|journal=Theoretical Computer Science|language=en|volume=209|issue=1-2|pages=237–260|doi=10.1016/S0304-3975(97)00115-1|issn=0304-3975}}</ref>

* 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.

== References ==

{{Reflist}}

[[Category:Linear programming]]

[[Category:NP-hard problems]]