The Complexity of Finite-Valued CSPs
From MaRDI portal
Publication:3177814
DOI10.1145/2974019zbMath1410.68177arXiv1210.2987MaRDI QIDQ3177814
Johan Thapper, Stanislav Živný
Publication date: 2 August 2018
Published in: Journal of the ACM, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1210.2987
complexity; discrete optimization; dichotomy; valued constraint satisfaction problems; finite-valued constraint satisfaction problems
68Q25: Analysis of algorithms and problem complexity