id: 06102432
dt: a
an: 06102432
au: Leithäuser, Neele; Krumke, Sven O.; Merkert, Maximilian
ti: Approximating infeasible 2VPI-systems.
so: Golumbic, Martin Charles (ed.) et al., Graph-theoretic concepts in computer
    science. 38th international workshop, WG 2012, Jerusalem, Israel, June
    26‒28, 2012. Revised selcted papers. Berlin: Springer (ISBN
    978-3-642-34610-1/pbk). Lecture Notes in Computer Science 7551, 225-236
    (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-34611-8_24
ab: Summary: 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.
rv: