Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Every 2-CSP Allows Nontrivial Approximation
KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.ORCID-id: 0000-0002-5379-345X
2005 (engelsk)Inngår i: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, s. 740-746Konferansepaper, Publicerat paper (Fagfellevurdert)
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 provably better than picking a random assignment. To be more precise assume that each variable can take values in [d] and that each constraint rejects t out of the d2 possible input pairs. Then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, on expectation, within a factor (1- t/d2(1- c/d2 log d)) of optimal.

sted, utgiver, år, opplag, sider
2005. s. 740-746
HSV kategori
Identifikatorer
URN: urn:nbn:se:kth:diva-63001DOI: 10.1145/1060590.1060700Scopus ID: 2-s2.0-26944485593ISBN: 1-58113-960-8 (tryckt)OAI: oai:DiVA.org:kth-63001DiVA, id: diva2:481480
Konferanse
the 37th Annual ACM Symposium on Theory of Computing
Merknad
QC 20120123Tilgjengelig fra: 2012-01-21 Laget: 2012-01-21 Sist oppdatert: 2022-06-24bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Person

Håstad, Johan

Søk i DiVA

Av forfatter/redaktør
Håstad, Johan
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 54 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf