MP11 M INIMUM U NSATISFYING L INEAR S UBSYSTEM

     
• I NSTANCE : System Ax=b of linear equations, where A is an integer -matrix, and b is an integer m -vector.
• S OLUTION : A rational n -vector .
• M EASURE : The number of equations that are not satisfied by x .

• Bad News: Not in A PX [ 21 ].
• Comment: Not approximable within for any unless NP QP [ 22 ]. If the system consists of relations (> or ) the problem is even harder to approximate; there is a transformation from M INIMUM D OMINATING S ET 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 within for any . Approximability results for even more variants of the problem can be found in [ 9 ].