Minimum relevant variables in linear system: Difference between revisions

Revision as of 01:02, 28 October 2021

Latest revision as of 01:52, 22 March 2024

(3 intermediate revisions by 3 users not shown)

Line 1:

'''MINimumMinimum Relevantrelevant Variablesvariables in Linearlinear Systemsystem''' ('''Min-RVLS''') 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 name=":1">{{cite journal |last1=Amaldi |first1=Edoardo |last2=Kann |first2=Viggo |title=On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems |journal=Theoretical Computer Science |date=December 1998 |volume=209 |issue=1-21–2 |pages=237–260 |doi=10.1016/S0304-3975(97)00115-1 |doi-access=free }}</ref>

* A binary relation ''R'', which is one of {=, ≥, >, ≠};

Line 23:

== Related problems ==

In '''MINimumminimum Unsatisfiedunsatisfied Linearlinear Relationsrelations''' ('''Min-ULR'''), we are given a binary relation ''R'' and a linear system ''A x'' ''R'' ''b'', which is now assumed to be ''infeasible''. The goal is to find a vector ''x'' that violates as few relations as possible, while satisfying all the others.

Min-ULR[≠] is trivially solvable, since any system with real variables and a finite number of inequality constraints is feasible. As for the other three variants:

* Min-ULR[=,>,≥] are NP-hard even with homogeneous systems and bipolar coefficients (coefficients in {1,-1}). <ref name=":0">{{cite journal |last1=Amaldi |first1=Edoardo |last2=Kann |first2=Viggo |title=The complexity and approximability of finding maximum feasible subsystems of linear relations |journal=Theoretical Computer Science |date=August 1995 |volume=147 |issue=1-21–2 |pages=181–210 |doi=10.1016/0304-3975(94)00254-G |doi-access=free }}</ref>

* The NP-complete problem [[Minimum feedback arc set]] reduces to Min-ULR[≥], with exactly one 1 and one -1 in each constraint, and all right-hand sides equal to 1.<ref name=":2">{{cite journal |last1=Sankaran |first1=Jayaram K |title=A note on resolving infeasibility in linear programs by constraint relaxation |journal=Operations Research Letters |date=February 1993 |volume=13 |issue=1 |pages=19–20 |doi=10.1016/0167-6377(93)90079-V }}</ref>

* Min-ULR[=,>,≥] are polynomial if the number of variables ''n'' is constant: they can be solved polynomially using an algorithm of Greer<ref>{{cite book |last1=Greer |first1=R. |title=Trees and Hills: Methodology for Maximizing Functions of Systems of Linear Relations |date=2011 |publisher=Elsevier |isbn=978-0-08-087207-0 }}{{pn|date=October 2021}}</ref> in time <math>O(n\cdot m^n / 2^{n-1})</math>.

* Min-ULR[=,>,≥] are linear if the number of constraints ''m'' is constant, since all subsystems can be checked in time ''O''(''n'').

*Min-ULR[≥] is polynomial in some special case.<ref name=":2" />

Line 36:

*Min-ULR[=] cannot be approximated within a factor of <math>2^{\log^{1-\varepsilon}n}</math>, for any <math>\varepsilon>0</math>, unless NP is contained in [[DTIME]](<math>n^{\operatorname{polylog}(n)}</math>).<ref>{{cite journal |last1=Arora |first1=Sanjeev |last2=Babai |first2=László |last3=Stern |first3=Jacques |last4=Sweedyk |first4=Z |title=The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations |journal=Journal of Computer and System Sciences |date=April 1997 |volume=54 |issue=2 |pages=317–331 |doi=10.1006/jcss.1997.1472 |doi-access=free }}</ref>

In the complementary problem '''MAXimummaximum Feasiblefeasible Linearlinear Subsystemsubsystem''' ('''Max-FLS'''), the goal is to find a maximum subset of the constraints that can be satisfied simultaneously.<ref name=":0" />

* Max-FLS[≠] can be solved in polynomial time.