Minimum relevant variables in linear system: Difference between revisions

Revision as of 12:05, 7 January 2019

Revision as of 12:09, 7 January 2019

Line 4:

== Definition ==

A Min-RVLS problem is defined by:<ref name=":1">{{Cite journal|date=1998-12-06|title=On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems|url=https://www.sciencedirect.com/science/article/pii/S0304397597001151|journal=Theoretical Computer Science|language=en|volume=209|issue=1-2|pages=237–260|doi=10.1016/S0304-3975(97)00115-1|issn=0304-3975}}</ref>

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

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.

* 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[=], Min-ULR[>] and Min-ULR[,≥] are NP-hard even with homogeneous systems and bipolar coefficients (coefficients in {1,-1}). <ref name=":0" />

* 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. In some special cases, Min-ULR[≥] can be solved in polynomial time.<ref name=":2">{{Cite journal|date=1993-02-01|title=A note on resolving infeasibility in linear programs by constraint relaxation|url=https://www.sciencedirect.com/science/article/pii/016763779390079V|journal=Operations Research Letters|language=en|volume=13|issue=1|pages=19–20|doi=10.1016/0167-6377(93)90079-V|issn=0167-6377}}</ref>

* IfMin-ULR[=,>,≥] are polynomial if the number of variables ''n'' is constant,: then Min-ULR[=], Min-ULR[>] and Min-ULR[≥]they can be solved polynomially using an algorithm of Greer.<ref>{{Cite book|url=https://books.google.co.il/books?hl=iw&lr=&id=DRxEqwzbb2UC&oi=fnd&pg=PP1&dq=Trees+and+hills:+Methodology+for+maximizing+functions+of+systems+of+linear+relations,&ots=50EXPaJ_VC&sig=uL5nVIhh146iH1sYf--cLHvntcM&redir_esc=y#v=onepage&q=Trees%20and%20hills:%20Methodology%20for%20maximizing%20functions%20of%20systems%20of%20linear%20relations,&f=false|title=Trees and Hills: Methodology for Maximizing Functions of Systems of Linear Relations|last=Greer|first=R.|date=2011-08-18|publisher=Elsevier|isbn=9780080872070|language=en}}</ref> Thein run-time is <math>O(n\cdot m^n / 2^{n-1})</math>.

* IfMin-ULR[=,>,≥] are linear if the number of constraints ''m'' is constant, then Min-ULR[=], Min-ULR[>] and Min-ULR[≥] are trivial 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''+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,0,1}).

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">{{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>