The approximability of MAX CSP with fixed-value constraints

DOI10.1145/1391289.1391290zbMath1325.68105OpenAlexW1979388565MaRDI QIDQ3451267

Peter Jonsson, Vladimir G. Deǐneko, Andrei A. Krokhin, Mikael Klasson

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/6288/1/6288.pdf

zbMATH Keywords

supermodularitydichotomymaximum constraint satisfactioncomplexity of approximationMonge properties

Mathematics Subject Classification ID

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

Related Items (11)

The Complexity of General-Valued CSPs ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ The Expressive Power of Binary Submodular Functions ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Unnamed Item ⋮ The Complexity of Valued CSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ On the complexity of submodular function minimisation on diamonds ⋮ The expressive power of binary submodular functions ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Unnamed Item

This page was built for publication: The approximability of MAX CSP with fixed-value constraints