The power of linear programming for general-valued CSPs Journal Article


Author(s): Kolmogorov, Vladimir; Thapper, Johan; Živný, Stanislav
Article Title: The power of linear programming for general-valued CSPs
Affiliation IST Austria
Abstract: A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. Finite-valued constraint languages contain functions that take on rational costs and general-valued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs). Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a general-valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2. Using these results, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees.
Journal Title: SIAM Journal on Computing
ISSN: 0097-5397
Publisher: SIAM  
Date Published: 2015-02-01
Start Page: 1
End Page: 36
URL:
DOI: 10.1137/130945648
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work