Next: MAXIMUM HYPERPLANE CONSISTENCY Up: Mathematical Programming Previous: MAXIMUM SATISFYING LINEAR SUBSYSTEM Index

### MINIMUM UNSATISFYING LINEAR SUBSYSTEM

- INSTANCE: System Ax=b of linear equations, where A is an integer m x n-matrix, and b is an integer m-vector.

- SOLUTION: A rational n-vector .

- MEASURE: The number of equations that are not satisfied by x.

- Bad News: Not in APX [33].

- Comment: Not approximable within for any unless NPQP [33]. 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 within for any . Approximability results for even more variants of the problem can be found in [16].