Minimum relevant variables in linear system: Difference between revisions

Revision as of 01:02, 28 October 2021

Revision as of 01:03, 28 October 2021

Line 4:

== Definition ==

A Min-RVLS problem is defined by:<ref name=":1">{{cite journal |last1=Amaldi |first1=Edoardo |last2=Kann |first2=Viggo |title=On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems |journal=Theoretical Computer Science |date=December 1998 |volume=209 |issue=1-21–2 |pages=237–260 |doi=10.1016/S0304-3975(97)00115-1 |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 |last1=Amaldi |first1=Edoardo |last2=Kann |first2=Viggo |title=The complexity and approximability of finding maximum feasible subsystems of linear relations |journal=Theoretical Computer Science |date=August 1995 |volume=147 |issue=1-21–2 |pages=181–210 |doi=10.1016/0304-3975(94)00254-G |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 |last1=Sankaran |first1=Jayaram K |title=A note on resolving infeasibility in linear programs by constraint relaxation |journal=Operations Research Letters |date=February 1993 |volume=13 |issue=1 |pages=19–20 |doi=10.1016/0167-6377(93)90079-V }}</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 |last1=Greer |first1=R. |title=Trees and Hills: Methodology for Maximizing Functions of Systems of Linear Relations |date=2011 |publisher=Elsevier |isbn=978-0-08-087207-0 }}{{pn}}</ref> in time <math>O(n\cdot m^n / 2^{n-1})</math>.