Change search
ReferencesLink to record
Permanent link

Direct link
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 (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
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 03029743
Keyword [en]
Algorithms, Approximation theory, Computational complexity, Computer science, Polynomials, Problem solving, Theorem proving
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-63004ScopusID: 2-s2.0-33750050257ISBN: 3540380442ISBN: 978-354038044-3OAI: diva2:481484
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

QC 20141125

Available from: 2012-01-21 Created: 2012-01-21 Last updated: 2014-11-25Bibliographically approved

Open Access in DiVA

No full text


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
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

Total: 17 hits
ReferencesLink to record
Permanent link

Direct link