Paper Info
Title
Approximating infeasible 2VPI-systems
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 xi−xj=cij 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.
Year
DOI
Venue
2012
10.1007/978-3-642-34611-8_24
WG
Keywords
Field
DocType
main result,related maximization problem maxfs2,folklore result,constant factor approximation,feasible inequality,minimum weight,associated constraint graph,gaussian elimination,constraint graph,approximating infeasible,problem minfs2
Discrete mathematics,Mathematical optimization,Combinatorics,System of linear equations,Of the form,Computer science,Constraint graph,Minimum weight,Gaussian elimination,Arboricity,Maximization,Computation
Conference
Volume
ISSN
Citations 
7551
0302-9743
0
PageRank 
References 
Authors
0.34
11
3
Name
Order
Citations
PageRank
Neele Leithäuser100.34
Sven O. Krumke230836.62
Maximilian Merkert331.42