Change search
ReferencesLink to record
Permanent link

Direct link
Towards sharp inapproximability for any 2-CSP
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0001-8217-0158
2007 (English)In: 48th Annual IEEE Symposium On Foundations Of Computer Science, Proceedings, 2007, 307-317 p.Conference paper (Refereed)
Abstract [en]

We continue the recent line, of work on the connection between semidefinite programming-based approximation algorithms and the Unique Games Conjecture. Given any boolean 2-CSP (or more generally, any nonnegative objective function on two boolean variables), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. The key objects in our analysis are the vector triples arising when doing clause-by-clause analysis of algorithms based on semidefinite programming. Given a. weighted set of such triples of a certain restricted type, which are "hard" to round in a certain sense, we obtain a Unique Games-based inapproximability matching this "hardness" of rounding the set of vector triples. Conversely, any instance together with an SDP solution can be viewed as a set of vector triples, and we show that we can always find an assignment to the instance which is at least as good as the "hardness" of rounding the corresponding set of vector triples. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that MAX 2-AND is hard to approximate within 0.87435. This improves upon the best previous hardness of alpha(GW) + epsilon approximate to 0.87856, and comes very close to matching the approximation ratio of the best algorithm known, 0.87401. It also establishes that balanced instances of MAX 2-AND, i.e., instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor alpha(GW).

Place, publisher, year, edition, pages
2007. 307-317 p.
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-41059DOI: 10.1109/FOCS.2007.4389502ISI: 000252161900028ScopusID: 2-s2.0-46749105182ISBN: 978-0-7695-3010-9OAI: diva2:444749
48th Annual IEEE Symposium on Foundations of Computer Science Location: Providence, RI Date: OCT 20-23, 2007

QC 20150703

Available from: 2011-09-30 Created: 2011-09-23 Last updated: 2015-07-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 28 hits
ReferencesLink to record
Permanent link

Direct link