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

DOI10.1007/978-3-540-74510-5_20zbMath1188.68153OpenAlexW1602724486MaRDI QIDQ3499775

Fredrik Kuivinen, Peter Jonsson, Andrei A. Krokhin

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

complexityapproximabilitymaximum constraint satisfaction

Mathematics Subject Classification ID

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

Related Items (3)

Genetic based discrete particle swarm optimization for elderly day care center timetabling ⋮ Approximability Distance in the Space of H-Colourability Problems ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture

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