Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Approximating infeasible 2VPI-systems

 
: Leithäuser, N.; Krumke, S.O.; Merkert, M.

:

Golumbic, M.C.:
Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012. Revised selected papers
Heidelberg: Springer, 2012 (Lecture Notes in Computer Science 7551)
ISBN: 3-642-34610-3
ISBN: 978-3-642-34610-1
ISBN: 978-3-642-34611-8
pp.225-236
International Workshop on Graph-Theoretic 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 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.

: http://publica.fraunhofer.de/documents/N-254295.html