Minimum relevant variables in linear system: Difference between revisions

Revision as of 10:43, 8 January 2019

Revision as of 20:15, 9 January 2019

Line 32:

* 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" />

*Min-ULR[=,>,≥] can be approximated within ''n''&nbsp;+&nbsp;1 in polynomial time.<ref name=":1" />

*Min-ULR[>,≥] are [[Minimum dominating set|minimum-dominating-set]]-hard, even with homogeneous systems and ternary coefficients (in {-1−1,0,1}).

*Min-ULR[=] cannot be approximated within a factor of <math>2^{\log^{1-\epsilonvarepsilon}n}</math>, for any <math>\epsilonvarepsilon>0</math>, unless NP is contained in [[DTIME]](<math>n^{\operatorname{polylog}(n)}</math>). <ref>{{Cite journal|date=1997-04-01|title=The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations|url=https://www.sciencedirect.com/science/article/pii/S0022000097914720|journal=Journal of Computer and System Sciences|language=en|volume=54|issue=2|pages=317–331|doi=10.1006/jcss.1997.1472|issn=0022-0000}}</ref>

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

Line 41:

* Max-FLS[=] is NP-hard even with homogeneous systems and bipolar coefficients.

* . With integer coefficients, it is hard to approximate within <math>m^{\epsilonvarepsilon}</math>. With coefficients over GF[q], it is ''q''-approximable.

* Max-FLS[>] and Max-FLS[≥] are NP-hard even with homogeneous systems and bipolar coefficients. They are 2-approximable, but they cannot be approximated within any smaller constant factor.

== Hardness of approximation ==

All four variants of Min-RVLS are hard to approximate. In particular all four variants cannot be approximated within a factor of <math>2^{\log^{1-\epsilonvarepsilon}n}</math>, for any <math>\epsilonvarepsilon>0</math>, unless NP is contained in [[DTIME]](<math>n^{\operatorname{polylog}(n)}</math>).<ref name=":1" />{{Rp|247-250}} The hardness is proved by reductions:

* There is a reduction from Min-ULR[=] to Min-RVLS[=]. It also applies to Min-RVLS[≥] and Min-RVLS[>], since each equation can be replaced by two complementary inequalities.