Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems

DOI10.1007/978-3-540-74510-5_20MaRDI QIDQ3499775zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Andrei Krokhin, Fredrik Kuivinen

Publication date 3 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74510-5_20

zbMATH Keywords

approximabilitycomplexitymaximum constraint satisfaction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• Hard constraint satisfaction problems have hard gaps at location 1
• The approximability of MAX CSP with fixed-value constraints
• scientific article; zbMATH DE number 1559517
• Complexity of approximating CSP with balance/hard constraints
• The approximability of constraint satisfaction problems

Cited in

(14)

• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• On regularity of Max-CSPs and Min-CSPs
• Hardness results for approximate pure Horn CNF formulae minimization
• On the NP-hardness of approximating ordering-constraint satisfaction problems
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• Complexity of approximating CSP with balance/hard constraints
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximability Distance in the Space of H-Colourability Problems
• Genetic based discrete particle swarm optimization for elderly day care center timetabling
• The approximability of MAX CSP with fixed-value constraints
• Tensor decomposition and approximation schemes for constraint satisfaction problems
• scientific article; zbMATH DE number 1559517 (Why is no real title available?)
• CSPs with global modular constraints: algorithms and hardness via polynomial representations
• Hard constraint satisfaction problems have hard gaps at location 1

This page was built for publication: Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems

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