The Approximability of Three-valued MAX CSP

DOI10.1137/S009753970444644XMaRDI QIDQ5470737zbMATH OpenFDO

Authors Peter Jonsson, Mikael Klasson, Andrei Krokhin

Publication date 1 June 2006

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

Full work available at URL https://doi.org/10.1137/S009753970444644X

zbMATH Keywords

dichotomyapproximabilitysupermodularitymaximum constraint satisfaction

Mathematics Subject Classification ID

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

Recommendations

• An approximation algorithm for MAX 3-SAT
• The approximability of MAX CSP with fixed-value constraints
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• scientific article; zbMATH DE number 2117169
• Conditional Hardness of Approximating Satisfiable Max 3CSP-q
• scientific article; zbMATH DE number 1303558

Cited in

(19)

• The complexity of surjective homomorphism problems-a survey
• Enumerating homomorphisms
• Conditional Hardness of Approximating Satisfiable Max 3CSP-q
• Introduction to the Maximum Solution Problem
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• The expressive power of binary submodular functions
• The approximability of MAX CSP with fixed-value constraints
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• The complexity of general-valued CSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• The complexity of valued CSPs
• The Expressive Power of Binary Submodular Functions
• Hard constraint satisfaction problems have hard gaps at location 1
• Minimum violation vertex maps and their applications to cut problems
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Classes of submodular constraints expressible by graph cuts
• On the complexity of submodular function minimisation on diamonds
• Minimization of locally defined submodular functions by optimal soft arc consistency

This page was built for publication: The Approximability of Three-valued MAX CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470737)