Next: MAXIMUM HYPERPLANE CONSISTENCY
Up: Mathematical Programming
Previous: MAXIMUM SATISFYING LINEAR SUBSYSTEM
System Ax=b of linear equations, where A is an integer
-matrix, and b is an integer m-vector.
A rational n-vector .
The number of equations that are not satisfied by x.
- Bad News:
Not in APX .
Not approximable within
unless NPQP .
If the system consists of relations (> or )
the problem is even
harder to approximate; there is a transformation from
MINIMUM DOMINATING SET to this problem.
If the variables are restricted to assume only binary values the problem is
NPO PB-complete both for equations and relations, and is not approximable
Approximability results for even more variants of the problem can be found in