We investigate the computational complexity of two classes of combinatorial optimization problems related to linear systems and study the relationship between their approximability properties. In the first class (MIN ULR) one wishes, given a possibly infeasible system of linear relations, to find a solution that violates as few relations as ... more >>>