The Approximability of Three-valued MAX CSP
From MaRDI portal
Publication:5470737
DOI10.1137/S009753970444644XzbMath1101.68042MaRDI QIDQ5470737
Mikael Klasson, Peter Jonsson, Andrei A. Krokhin
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
The Complexity of General-Valued CSPs ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ The Expressive Power of Binary Submodular Functions ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ Enumerating homomorphisms ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ The complexity of surjective homomorphism problems-a survey ⋮ The Complexity of Valued CSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ On the complexity of submodular function minimisation on diamonds ⋮ The expressive power of binary submodular functions ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Introduction to the Maximum Solution Problem
This page was built for publication: The Approximability of Three-valued MAX CSP
