Content deleted Content added
Citation bot (talk | contribs) Alter: issue. Formatted dashes. | Use this bot. Report bugs. | Suggested by Chris Capoccia | #UCB_toolbar |
m Dating maintenance tags: {{Pn}} |
||
Line 29:
* 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–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|date=October 2021}}</ref> in time <math>O(n\cdot m^n / 2^{n-1})</math>.
* Min-ULR[=,>,≥] are linear if the number of constraints ''m'' is constant, since all subsystems can be checked in time ''O''(''n'').
*Min-ULR[≥] is polynomial in some special case.<ref name=":2" />
| |||