Erel Segal: In progress
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-hardness|NP-hard]] and even hard to approximate.
== Definition ==
A Min-RVLS problem is defined by:<ref>Liquid error: wrong number of arguments (1 for 2)</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.
== Special case ==
The problem Min-RVLS[=] was presented by Garey and Johnson,<ref>Liquid error: wrong number of arguments (1 for 2)</ref> who called it "minimum weight solution to linear equations". They proved it was NP-hard, but did not consider approximations.
== References ==
[[Category:Linear programming]]
[[Category:NP-hard problems]]
The problem is known to be [[NP-hardness|NP-hard]] and even hard to approximate.
== Definition ==
A Min-RVLS problem is defined by:<ref>Liquid error: wrong number of arguments (1 for 2)</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.
== Special case ==
The problem Min-RVLS[=] was presented by Garey and Johnson,<ref>Liquid error: wrong number of arguments (1 for 2)</ref> who called it "minimum weight solution to linear equations". They proved it was NP-hard, but did not consider approximations.
== References ==
[[Category:Linear programming]]
[[Category:NP-hard problems]]
from Wikipedia - New pages [en] http://bit.ly/2GWzfuY
via IFTTT
No comments:
Post a Comment