Content deleted Content added
Citation bot (talk | contribs) m Alter: issue, url. Add: author pars. 1-4. Removed parameters. Formatted dashes. | You can use this bot yourself. Report bugs here. | User-activated. |
Removed URL that duplicated unique identifier. | You can use this tool yourself. Report bugs here. |
||
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
* 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
* 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>.
* Min-ULR[=,>,≥] are linear if the number of constraints ''m'' is constant, since all subsystems can be checked in time ''O''(''n'').
| |||