Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.