Content deleted Content added
Erel Segal (talk | contribs) In progress |
Erel Segal (talk | contribs) No edit summary |
||
Line 16:
== 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.
== Applications ==
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.<ref>{{Cite journal|last=Koehler|first=Gary J.|date=1991-11-01|title=Linear Discriminant Functions Determined by Genetic Search|url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.4.345|journal=ORSA Journal on Computing|volume=3|issue=4|pages=345–357|doi=10.1287/ijoc.3.4.345|issn=0899-1499}}</ref> The problem is known as the [[minimum feature set problem]].<ref>{{Cite journal|last=Van Horn|first=Kevin S.|last2=Martinez|first2=Tony R.|date=1994-03-01|title=The Minimum Feature Set Problem|url=http://dx.doi.org/10.1016/0893-6080(94)90082-5|journal=Neural Netw.|volume=7|issue=3|pages=491–494|doi=10.1016/0893-6080(94)90082-5|issn=0893-6080|via=}}</ref>
== References ==
| |||