Minimum relevant variables in linear system: Difference between revisions

Revision as of 11:11, 7 January 2019

Revision as of 11:25, 7 January 2019

Line 23:

In '''MINimum Unsatisfied Linear Relations''' ('''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.

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>{{Cite journal|date=1995-08-07|title=The complexity and approximability of finding maximum feasible subsystems of linear relations|url=https://www.sciencedirect.com/science/article/pii/030439759400254G|journal=Theoretical Computer Science|language=en|volume=147|issue=1-2|pages=181–210|doi=10.1016/0304-3975(94)00254-G|issn=0304-3975}}</ref>

* Max-FLS[≠] iscan polynomial,be butsolved Max-FLS[=]in ,polynomial Max-FLS[>]time. and
* Max-FLS[≥=] areis NP-hard even with homogeneous systems and bipolar coefficients.

* . With integer coefficients, it is hard to approximate within <math>m^{\epsilon}</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.

== References ==