Paper Info
Title
A polynomial-time algorithm for median-closed semilinear constraints.
Abstract
A subset of Q^n is called semilinear (or piecewise linear) if it is Boolean combination of linear half-spaces. We study the computational complexity of the constraint satisfaction problem (CSP) over the rationals when all the constraints are semilinear. When the sets are convex the CSP is polynomial-time equivalent to linear programming. A semilinear relation is convex if and only if it is preserved by taking averages. Our main result is a polynomial-time algorithm for the CSP of semilinear constraints that are preserved by applying medians. We also prove that this class is maximally tractable in the sense that any larger class of semilinear relations has an NP-hard CSP. To illustrate, our class contains all relations that can be expressed by linear inequalities with at most two variables (so-called TVPI constraints), but it also contains many non-convex relations, for example constraints of the form x in S for arbitrary finite subset S of Q, or more generally disjunctive constraints of the form x u003c c or y u003c d for constants c and d.
Year
Venue
Field
2018
arXiv: Computational Complexity
Discrete mathematics,Combinatorics,Rational number,Algorithm,Constraint satisfaction problem,Regular polygon,Linear programming,Time complexity,Piecewise linear function,Linear inequality,Mathematics,Computational complexity theory
DocType
Volume
Citations 
Journal
abs/1808.10068
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Manuel Bodirsky164454.63
Marcello Mamino2165.51