The Power of Linear Programming for General-Valued CSPs

DOI10.1137/130945648zbMath1456.68059arXiv1311.4219OpenAlexW2950298732MaRDI QIDQ5252658

Stanislav Živný, Johan Thapper, Vladimir Kolmogorov

Publication date: 2 June 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.4219

zbMATH Keywords

linear programmingsubmodularitybisubmodularityvalued constraint satisfactionfractional polymorphisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items (39)

CLAP: A New Algorithm for Promise CSPs ⋮ The Complexity of General-Valued CSPs ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ On a general framework for network representability in discrete optimization ⋮ A compact representation for minimizers of \(k\)-submodular functions ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ On planar valued CSPs ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Super-reparametrizations of weighted CSPs: properties and optimization perspective ⋮ Unnamed Item ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Complexity of Valued CSPs ⋮ Edge bipartization faster than \(2^k\) ⋮ Computing DM-decomposition of a partitioned matrix with rank-1 blocks ⋮ L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem ⋮ A compact representation for modular semilattices and its applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Minimum 0-extension problems on directed metrics ⋮ A Tractable Class of Binary VCSPs via M-Convex Intersection ⋮ Piecewise linear valued constraint satisfaction problems with fixed number of variables ⋮ On $k$-Submodular Relaxation ⋮ Testing the Complexity of a Valued CSP Language ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ On a General Framework for Network Representability in Discrete Optimization ⋮ A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract) ⋮ Gauges, loops, and polynomials for partition functions of graphical models

Uses Software

• JBool
• ToulBar2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colouring, constraint satisfaction, and complexity
• On the complexity of submodular function minimisation on diamonds
• Arc consistency for soft constraints
• Hard constraint satisfaction problems have hard gaps at location 1
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• The expressive power of binary submodular functions
• Soft arc consistency revisited
• Submodular function minimization
• Minimization of locally defined submodular functions by optimal soft arc consistency
• Consistency in networks of relations
• On the algebraic structure of combinatorial problems
• The partial constraint satisfaction problem: Facets and lifting theorems
• Conjunctive-query containment and constraint satisfaction
• Networks of constraints: Fundamental properties and applications to picture processing
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• The complexity of soft constraint satisfaction
• The Approximability of Constraint Satisfaction Problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Linear programming, width-1 CSPs, and robust satisfaction
• Complexity of conservative constraint satisfaction problems
• Robust Satisfiability for CSPs
• An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
• Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions
• Towards Minimizing k-Submodular Functions
• Min CSP on Four Elements: Moving beyond Submodularity
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Skew Bisubmodularity and Valued CSPs
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• The approximability of MAX CSP with fixed-value constraints
• An Algebraic Characterisation of Complexity for Valued Constraint
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
• Graphical Models, Exponential Families, and Variational Inference
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Synthesizing constraint expressions
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• The Complexity of Valued Constraint Satisfaction Problems
• Classifying the Complexity of Constraints Using Finite Algebras
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• Towards a Characterization of Constant-Factor Approximable Min CSPs
• Half-integrality, LP-branching and FPT Algorithms
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of conservative valued CSPs
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• An Algebraic Theory of Complexity for Discrete Optimization
• The complexity of satisfiability problems
• Robust satisfiability of constraint satisfaction problems
• Bisubmodular Function Minimization
• Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
• Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems: [Extended Abstract]

This page was built for publication: The Power of Linear Programming for General-Valued CSPs