Change search
ReferencesLink to record
Permanent link

Direct link
Beating a Random Assignment: Approximating Constraint Satisfaction Problems
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
2005 (English)Doctoral thesis, monograph (Other scientific)
Abstract [en]

An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. In the maximization version, Max CSP, each constraint has a weight and the objective is to find an assignment such that the weight of satisfied constraints is maximized. By specifying which types of constraints that are allowed we create subproblems to Max CSP. For example, an instance of Max kCSP only contains constraints that act over at most k different variables. Another problem is Max CSP(P), where P is a predicate, i.e., a Boolean function. In such an instance P is used to determine if a constraint is satisfied or not.

Both Max kCSP and Max CSP(P) are NP-hard to solve optimally for k ≥ 2 and predicates P that depend on at least two input values. Therefore, we consider efficient approximation algorithms for these two problems. A trivial algorithm is to assign all variables a random value. Somewhat surprisingly, Håstad showed that using this random assignment approach is essentially optimal for approximating Max CSP(P), for some predicates P. We call such predicates approximation resistant. Goemans and Williamson introduced an approximation method that relaxes problems into semidefinite programs. Using this method they show that for predicates P of arity two, it is possible to outperform a random assignment in approximating Max CSP(P). By extending this technique Zwick characterized all predicates of arity three as either approximation resistant or not.

In this thesis we consider predicates of arity larger than three. We extend the work of Håstad and the work of Samorodnitsky and Trevisan in order to show predicates to be approximation resistant. We also use semidefinite relaxation algorithms in order to show that predicates are not approximation resistant. In particular we show that predicates with few non-accepting inputs are approximation resistant and that predicates with few accepting inputs are not approximation resistant. We study predicates of arity four more closely and characterize 354 out of 400 predicate types.

Max kCSP is 2-k-approximated by a random assignment and previously no algorithms were known to outperform such an algorithm with more than a small constant factor. In this thesis a probabilistic

Ω (2k+log k-log log k)-approximation for Max kCSP is presented.

Place, publisher, year, edition, pages
Stockholm: KTH , 2005. , x, 102 p.
Trita-NA, ISSN 0348-2952 ; 0513
Keyword [sv]
National Category
Computer Science
URN: urn:nbn:se:kth:diva-215ISBN: 91-7178-051-3OAI: diva2:7927
Public defence
2005-06-14, E3, Osquars backe 14, Stockholm, 14:15
QC 20101020Available from: 2005-05-24 Created: 2005-05-24 Last updated: 2010-10-20Bibliographically approved

Open Access in DiVA

fulltext(595 kB)302 downloads
File information
File name FULLTEXT01.pdfFile size 595 kBChecksum SHA-1
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Hast, Gustav
By organisation
Numerical Analysis and Computer Science, NADA
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 302 downloads
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: 417 hits
ReferencesLink to record
Permanent link

Direct link