Minimum relevant variables in linear system: Difference between revisions

Revision as of 01:51, 22 March 2024

Latest revision as of 01:52, 22 March 2024

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:

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.