Approximating infeasible 2VPI-systems

It is a folklore result that testing whether a given system of equations with two variables per inequality (a 2VPI system) of the form x i -x j =c ij is solvable, can be done efficiently not only by Gaussian elimination but also by shortest-path computation on an associated constraint graph. However, when the system is infeasible and one wishes to delete a minimum weight set of inequalities to obtain feasibility (MinFs2 =), this task becomes NP-complete. Our main result is a 2-approximation for the problem MinFs2 = for the case when the constraint graph is planar using a primal-dual approach. We also give an -approximation for the related maximization problem MaxFs2 = where the goal is to maximize the weight of feasible inequalities. Here, denotes the arboricity of the constraint graph. Our results extend to obtain constant factor approximations for the case when the domains of the variables are further restricted.