2
$\begingroup$

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.

$\endgroup$

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.