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
On Nontrivial Approximation of CSPs
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2007 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Constraint satisfaction problems, more simply called CSPs are central in computer science, the most famous probably being Satisfiability, SAT, the basic NP-complete problem. In this talk we survey some results about the optimization version of CSPs where we want to satisfy as many constraints as possible. One very simple approach to a CSP is to give random values to the variables. It turns out that for some CSPs, one example being Max-3Sat, unless P=NP, there is no polynomial time algorithm that can achieve a an approximation ratio that is superior to what is obtained by this trivial strategy. Some other CSPs, Max-Cut being a prime example, do allow very interesting non-trivial approximation algorithms which do give an approximation ratio that is substantially better than that obtained by a random assignment. These results hint at a general classification problem of determining which CSPs do admit a polynomial time approximation algorithm that beats the random assignment by a constant factor. Positive results giving such algorithms tend to be based on semi-definite programming while the PCP theorem is the central tool for proving negative result. We describe many of the known results in the area and also discuss some of the open problems.

Place, publisher, year, edition, pages
2007.
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743
Keyword [en]
Algorithms, Approximation theory, Computational complexity, Computer science, Polynomials, Problem solving, Theorem proving
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-63004Scopus ID: 2-s2.0-33750050257ISBN: 3540380442 (print)ISBN: 9783540380443 (print)OAI: oai:DiVA.org:kth-63004DiVA: diva2:481484
Conference
9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006; Barcelona; Spain; 28-30 August 2006
Note

QC 20141125

Available from: 2012-01-21 Created: 2012-01-21 Last updated: 2017-03-29Bibliographically approved

Open Access in DiVA

No full text

Scopus

Authority records BETA

Håstad, Johan

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 28 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