The Power of Linear Programming for Valued CSPs
arXiv:1204.1079 · doi:10.1109/FOCS.2012.25
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. An instance of the problem is specified by a sum of cost 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. Using this result, 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.
Corrected a few typos
References in corpus (3)
Cited by in corpus (25)
- The power of linear programming for general-valued CSPs
- Maximizing k-Submodular Functions and Beyond
- A new look at reweighted message passing
- The complexity of conservative valued CSPs
- The complexity of finite-valued CSPs
- An Algebraic Theory of Complexity for Discrete Optimisation
- The power of Sherali-Adams relaxations for general-valued CSPs
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
- L-convexity on graph structures
- Half-integrality, LP-branching and FPT Algorithms
- A Galois Connection for Weighted (Relational) Clones of Infinite Size
- The power of linear programming for valued CSPs: a constructive characterization
- Sherali-Adams relaxations for valued CSPs
- Towards Minimizing k-Submodular Functions
- Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
- Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems
- On a general framework for network representability in discrete optimization
- Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- Testing Assignments to Constraint Satisfaction Problems
- Complexity of Discrete Energy Minimization Problems
- MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models
- Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets
- Computational Complexity of the Minimum Cost Homomorphism Problem on Three-Element Domains
- Three-Element Min-Sol and Conservative Min-Cost-Hom