The approximability of satisfying subsystems of linear systems
Viggo Kann, E. Amaldi · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1994
We study the computational complexity of the problem which consists, given a system of linear relations, of finding a solution satisfying as many relations as possible. This general combinatorial problem, referred to as maxfls, is considered for the four basic types of relations =, {ge}, > and {ne}. The problem can also be seen as a minimization problem, minulr, where we want to find a solution violating as few relations as possible. The problem is NP-hard for =, {ge} or > relations, even when restricted to homogeneous systems with bipolar coefficients, whereas it is trivial for {ne} relations. In this work we determine strong bounds on the approximability of various intractable variants, including constrained ones where the variables are restricted to take bounded discrete values. We show that the approximability of different variants can differ enormously. For example maxfls{sup {ge}} and maxfls{sup >} can be approximated within a factor of 2, while maxfls{sup =}, minulr{sup =}, minulr{sup {ge}} and minulr{sup >} cannot be approximated within any constant factor. Most of the constrained variants are maxpb- or minpb-complete, which means that they are among the hardest to approximate of all optimization problems with polynomially bounded objective functions.