Publication:2913811
From MaRDI portal
DOI10.4086/toc.2012.v008a011zbMath1255.68303MaRDI QIDQ2913811
Yuan Zhou, Venkatesan Guruswami
Publication date: 27 September 2012
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2012.v008a011
approximation algorithms; hardness of approximation; unique games conjecture; exact hitting set; Horn-SAT
90C59: Approximation methods and heuristics in mathematical programming
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Nearly Optimal NP-Hardness of Unique Coverage, Complexity of approximating CSP with balance/hard constraints, Towards a characterization of constant-factor approximable finite-valued CSPs
Cites Work