The approximability of MAX CSP with fixed-value constraints

DOI10.1145/1391289.1391290MaRDI QIDQ3451267zbMATH OpenOpenAlexFDO

Authors Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei Krokhin

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

complexity of approximationdichotomymaximum constraint satisfactionMonge propertiessupermodularity

Mathematics Subject Classification ID

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

Recommendations

• The Approximability of Three-valued MAX CSP
• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• Supermodularity on chains and complexity of maximum constraint satisfaction
• STACS 2004
• Supermodular functions and the complexity of MAX CSP

Cited in

(28)

• Towards a characterization of constant-factor approximable finite-valued CSPs
• On the Hamming distance of constraint satisfaction problems.
• On regularity of Max-CSPs and Min-CSPs
• Supermodular functions and the complexity of MAX CSP
• The Expressive Power of Binary Submodular Functions
• Approximability of the Maximum Solution Problem for Certain Families of Algebras
• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• Approximability of Integer Programming with Generalised Constraints
• Supermodularity on chains and complexity of maximum constraint satisfaction
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• The complexity of valued CSPs
• Minimum violation vertex maps and their applications to cut problems
• The power of linear programming for general-valued CSPs
• The complexity of general-valued CSPs
• STACS 2004
• Complexity and Approximability of Parameterized MAX-CSPs
• The Approximability of Three-valued MAX CSP
• Automata, Languages and Programming
• The complexity of conservative valued CSPs
• Approximability of Bounded Occurrence Max Ones
• Optimal polynomial-time compression for Boolean Max CSP
• On the complexity of submodular function minimisation on diamonds
• Optimal polynomial-time compression for Boolean Max CSP
• Hard constraint satisfaction problems have hard gaps at location 1
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• The expressive power of binary submodular functions
• A branch and bound algorithm for numerical Max-CSP
• Approximability of clausal constraints

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

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