Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
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.
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> ▼
* 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>{{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>
* If the number of variables ''n'' is constant, then Min-ULR[=], Min-ULR[>] and Min-ULR[≥] 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> The run-time is <math>O(n\cdot m^n / 2^{n-1})</math>.
* 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'').
▲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>
* Max-FLS[≠] can be solved in polynomial time.
| |||