Jump to content

Minimum relevant variables in linear system

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Erel Segal (talk | contribs) at 08:26, 7 January 2019 (Starting). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

The Min-RVLS problem[1] (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.


  1. ^ "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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Minimum_relevant_variables_in_linear_system&oldid=877216178"