Content deleted Content added
m typo: fro (via WP:JWB) |
m Open access bot: doi added to citation with #oabot. |
||
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|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|last1=Amaldi|first1=Edoardo|last2=Kann|first2=Viggo|doi-access=free}}</ref>
* A binary relation ''R'', which is one of {=, ≥, >, ≠};
Line 27:
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[=,>,≥] are NP-hard even with homogeneous systems and bipolar coefficients (coefficients in {1,-1}). <ref name=":0">{{Cite journal|date=1995-08-07|title=The complexity and approximability of finding maximum feasible subsystems of linear relations|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|last1=Amaldi|first1=Edoardo|last2=Kann|first2=Viggo|doi-access=free}}</ref>
* 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. <ref name=":2">{{Cite journal|date=1993-02-01|title=A note on resolving infeasibility in linear programs by constraint relaxation|journal=Operations Research Letters|language=en|volume=13|issue=1|pages=19–20|doi=10.1016/0167-6377(93)90079-V|issn=0167-6377|last1=Sankaran|first1=Jayaram K.}}</ref>
* Min-ULR[=,>,≥] are polynomial if the number of variables ''n'' is constant: they can be solved polynomially using an algorithm of Greer<ref>{{Cite book|url=https://books.google.com/?id=DRxEqwzbb2UC&pg=PP1&dq=Trees+and+hills:+Methodology+for+maximizing+functions+of+systems+of+linear+relations,#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> in time <math>O(n\cdot m^n / 2^{n-1})</math>.
Line 34:
*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}).
*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|date=1997-04-01|title=The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations|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|last1=Arora|first1=Sanjeev|last2=Babai|first2=László|last3=Stern|first3=Jacques|last4=Sweedyk|first4=Z.|doi-access=free}}</ref>
In the complementary problem '''MAXimum Feasible Linear Subsystem''' ('''Max-FLS'''), the goal is to find a maximum subset of the constraints that can be satisfied simultaneously.<ref name=":0" />
| |||