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
EVERY 2-CSP ALLOWS NONTRIVIAL APPROXIMATION
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2008 (English)In: Computational Complexity, ISSN 1016-3328, E-ISSN 1420-8954, Vol. 17, no 4, 549-566 p.Article in journal (Refereed) Published
Abstract [en]

We use semidefinite programming to prove that any constraint satisfaction problem in two variables over any domain allows an efficient approximation algorithm that does better than picking a random assignment. Specifically we consider the case when each variable can take values in [d] and that each constraint rejects t out of the d(2) possible input pairs. Then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, in expectation, within a factor 1 - t/d(2) + ct/d(4) log d of optimal, improving on the trivial bound of 1 - t/d(2).

Place, publisher, year, edition, pages
2008. Vol. 17, no 4, 549-566 p.
Keyword [en]
Semi-definite programming, constraint satisfaction, approximation, algorithms, combinatorial optimization, constraint satisfaction, satisfiability, problems, linear-equations, 2 variables, semidefinite, algorithms, cut
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-18021DOI: 10.1007/s00037-008-0256-yISI: 000261329700006Scopus ID: 2-s2.0-57349107952OAI: oai:DiVA.org:kth-18021DiVA: diva2:336066
Note
QC 20100525Available from: 2010-08-05 Created: 2010-08-05 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Håstad, Johan

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
In the same journal
Computational Complexity
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 56 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