A characterization of approximation resistance for even k-partite CSPs
2013 (English)In: ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, New York: Association for Computing Machinery (ACM), 2013, 187-196 p.Conference paper (Refereed)
A constraint satisfaction problem (CSP) is said to be approximation resistant if it is hard to approximate better than the trivial algorithm which picks a uniformly random assignment. Assuming the Unique Games Conjecture, we give a characterization of approximation resistance for k-partite CSPs defined by an even predicate.
Place, publisher, year, edition, pages
New York: Association for Computing Machinery (ACM), 2013. 187-196 p.
approximation resistance, unique games conjecture
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-136052DOI: 10.1145/2422436.2422459ScopusID: 2-s2.0-84873348647ISBN: 978-145031859-4OAI: oai:DiVA.org:kth-136052DiVA: diva2:670212
2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013; Berkeley, CA; United States; 9 January 2013 through 12 January 2013
QC 201312032013-12-032013-12-032013-12-03Bibliographically approved