Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
From MaRDI portal
Publication:935141
DOI10.1016/J.TCS.2008.03.015zbMath1154.90011OpenAlexW2090795232MaRDI QIDQ935141
Martin C. Cooper, David A. Cohen, Peter G. Jeavons
Publication date: 31 July 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://ora.ox.ac.uk/objects/uuid:20aa2a6f-ef85-44d3-ba1d-763e9950428d
submodularitydiscrete optimizationconstraint satisfaction problemmodular decompositiontractabilityvalued constraint satisfactionmajority operationtournament operation
Related Items (15)
Sherali-Adams Relaxations for Valued CSPs ⋮ On planar valued CSPs ⋮ Modularity-based decompositions for valued CSP ⋮ Classes of submodular constraints expressible by graph cuts ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Tree-representation of set families and applications to combinatorial decompositions ⋮ A complexity classification of spin systems with an external field ⋮ Hybrid tractability of valued constraint problems ⋮ The Complexity of Valued CSPs ⋮ The expressive power of binary submodular functions ⋮ A Representation Theorem for Union-Difference Families and Application ⋮ The complexity of approximating conservative counting CSPs ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Arc consistency for soft constraints
- Solving weighted CSP by maintaining arc consistency
- High-order consistency in valued constraint satisfaction
- Comments on Mohr and Henderson's path consistency algorithm
- A dichotomy theorem for maximum generalized satisfiability problems.
- Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
- An optimal k-consistency algorithm
- The ellipsoid method and its consequences in combinatorial optimization
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Minimizing symmetric submodular functions
- Submodular functions and electrical networks
- Horn functions and submodular Boolean functions
- A note on the minimization of symmetric and general submodular functions
- Linear-time modular decomposition of directed graphs
- Realization of set functions as cut functions of graphs and hypergraphs
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A fully combinatorial algorithm for submodular function minimization.
- Reduction operations in fuzzy or valued constraint satisfaction
- Supermodular functions and the complexity of MAX CSP
- The complexity of soft constraint satisfaction
- Minimum cost and list homomorphisms to semicomplete digraphs
- Combinatorial problems raised from 2-semilattices
- Submodular functions and optimization.
- The Approximability of Constraint Satisfaction Problems
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Efficient and Practical Algorithms for Sequential Modular Decomposition
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Maximum Constraint Satisfaction on Diamonds
- An Algebraic Characterisation of Complexity for Valued Constraint
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Minimum cuts, modular functions, and matroid polyhedra
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Optimal cooperation and submodularity for computing Potts partition functions with a large number of states
- A Faster Scaling Algorithm for Minimizing Submodular Functions
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- The Approximability of Three-valued MAX CSP
- Bisubmodular Function Minimization
- Principles and Practice of Constraint Programming – CP 2003
- Principles and Practice of Constraint Programming – CP 2004
- Tractable constraints on ordered domains
This page was built for publication: Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
