Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Approximating Infeasible 2VPI-Systems
verfasst von : Neele Leithäuser, Sven O. Krumke, Maximilian Merkert
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.