Minimum relevant variables in linear system: Difference between revisions

Revision as of 08:33, 7 January 2019

Revision as of 08:35, 7 January 2019

Line 4:

== Definition ==

A Min-RVLS problemisproblem is 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 {=, ≥, >, ≠};

Line 13:

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>{{Cite web|url=https://www.semanticscholar.org/paper/Computers-and-Intractability:-A-Guide-to-the-Theory-Garey-Johnson/1e3b61f29e5317ef59d367e1a53ba407912d240e|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|last=Johnson|first=David S.|last2=Garey|first2=M. R.|date=1979|website=www.semanticscholar.org|language=en|access-date=2019-01-07}}</ref> who called it "minimum weight solution to linear equations". They proved it was NP-hard, but did not consider approximations.

== References ==