Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP

DOI10.1145/1993636.1993725zbMath1288.68281arXiv1006.3368OpenAlexW2066467737MaRDI QIDQ5419137

Yuichi Yoshida

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.3368

zbMATH Keywords

constraint satisfaction problemsproperty testinglinear programmingsrounding schemesconstant-time approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of mathematical programming (90C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

Testing list \(H\)-homomorphisms ⋮ Testing the \((s,t)\) connectivity of graphs and digraphs ⋮ Unnamed Item

This page was built for publication: Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP