The maximum feasible subsystem problem, which is generally NP-hard [1].

Are there special algorithms in case of only 2 variables (2D linear constraints)? The problem seems to be a lot less complex in my humble opinion but is this true? Can you guys point me to any algorithms/papers for this limited case with reduced computational complexity?

[1] E. Amaldi and V. Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations Theoretical Computer Science, vol. 147, pp. 181–210, 1993.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.