On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
We investigate the computational complexity of two closely related classes of combinatorial optimization problems for linear systems which arise in various fields such as machin...