Optimal inapproximability with universal factor graphs

DOI10.1145/3631119MaRDI QIDQ6922350zbMATH OpenFDO

Authors Per Austrin, Jonah Brown-Cohen, Johan Hastad

Publication date 1 October 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

zbMATH Keywords

hardness of approximationfactor graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Computational aspects of satisfiability (68R07)

This page was built for publication: Optimal inapproximability with universal factor graphs

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