The power of linear programming for general-valued CSPs Kolmogorov, Vladimir Thapper, Johan Živný, Stanislav 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. SIAM 2015 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/2271 Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued CSPs. <i>SIAM Journal on Computing</i>. 2015;44(1):1-36. doi:<a href="https://doi.org/10.1137/130945648">10.1137/130945648</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1137/130945648 info:eu-repo/semantics/altIdentifier/wos/000353967100001 info:eu-repo/semantics/altIdentifier/arxiv/1311.4219 info:eu-repo/semantics/openAccess