Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Approximating infeasible 2VPIsystems
 Golumbic, M.C.: Graphtheoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, June 2628, 2012. Revised selected papers Heidelberg: Springer, 2012 (Lecture Notes in Computer Science 7551) ISBN: 3642346103 ISBN: 9783642346101 ISBN: 9783642346118 pp.225236 
 International Workshop on GraphTheoretic Concepts in Computer Science (WG) <38, 2012, Jerusalem> 

 English 
 Conference Paper 
 Fraunhofer ITWM () 
Abstract
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 shortestpath 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 NPcomplete. Our main result is a 2approximation for the problem MinFs2 = for the case when the constraint graph is planar using a primaldual 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.