Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2010 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 39, no 6, 2430-2463 p.Article in journal (Refereed) Published
Abstract [en]

We continue the recent line of work on the connection between semidefinite programming (SDP)-based approximation algorithms and the unique games conjecture. Given any Boolean 2-CSP (or, more generally, any Boolean 2-CSP with real-valued "predicates"), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. Furthermore, we give an SDP-based approximation algorithm and show that the approximation ratio of this algorithm on a certain restricted type of instances is exactly the inapproximability ratio yielded by our hardness result. 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 unique games-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 aGW and that Max Cut is not the hardest 2-CSP.

Place, publisher, year, edition, pages
2010. Vol. 39, no 6, 2430-2463 p.
Keyword [en]
constraint satisfaction problems, approximation algorithms, unique games conjecture, semidefinite programming
National Category
Computer Science Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-27867DOI: 10.1137/070711670ISI: 000277585000015Scopus ID: 2-s2.0-77952280579OAI: oai:DiVA.org:kth-27867DiVA: diva2:385769
Funder
Swedish Research Council, 50394001
Note

QC 20150701

Available from: 2011-01-12 Created: 2011-01-03 Last updated: 2017-12-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Austrin, Per

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
In the same journal
SIAM journal on computing (Print)
Computer ScienceComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 106 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf