diva-portal.org

# Digitala Vetenskapliga Arkivet

Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Annat format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annat språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf
Beating a Random Assignment: Approximating Constraint Satisfaction Problems
KTH, Skolan för datavetenskap och kommunikation (CSC), Numerisk Analys och Datalogi, NADA.
2005 (Engelska)Doktorsavhandling, monografi (Övrigt vetenskapligt)
##### 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.

##### Ort, förlag, år, upplaga, sidor
Stockholm: KTH , 2005. , s. x, 102
##### Serie
Trita-NA, ISSN 0348-2952 ; 0513
Datalogi
##### Nationell ämneskategori
Datavetenskap (datalogi)
##### Identifikatorer
ISBN: 91-7178-051-3 (tryckt)OAI: oai:DiVA.org:kth-215DiVA, id: diva2:7927
##### Disputation
2005-06-14, E3, Osquars backe 14, Stockholm, 14:15

#### Open Access i DiVA

##### Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 595 kBChecksumma SHA-1
d6353c350f762e9daa199e2c8c01951f098933885b0c21c3af0160b66a7f5cd5542173a0
Typ fulltextMimetyp application/pdf

#### Sök vidare i DiVA

Hast, Gustav
##### I ämnet
Datavetenskap (datalogi)

#### Sök vidare utanför DiVA

Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.
isbn
urn-nbn

#### Altmetricpoäng

isbn
urn-nbn
Totalt: 1140 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Annat format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annat språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf
v. 2.43.0
| | |