Take the 2-minute tour ×
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.

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

Question:
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?

References:
[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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.