Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
An extension of the PPSZ Algorithm to Infinite-Domain Constraint Satisfaction Problems
Linköping University, Department of Computer and Information Science, Software and Systems.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
En utökning av PPSZ Algoritmen till Oändlig-Domän Constraint Satisfaction Problem (Swedish)
Abstract [en]

The PPSZ algorithm (Paturi et al., FOCS 1998) is the fastest known algorithm for solving k-SAT when k >= 4. Hertli et al. recently extended the algorithm to solve (d, k)-Clause Satisfaction problems ((d,k)-ClSP) for which it is the fastest known algorithm for all k >= 3 (Hertli et al. CP 2016). We analyze their algorithm and extend it to solve problems over an infinite domain. More specifically we show how the extended algorithm can solve problems that have an infinite domain but where we can, for each instance of the problem, find a finite subset of the domain which has the following properties: If there exists a solution to the problem instance, then there exists a solution using only values from this subset and the size of this subset is polynomial in the size of the problem instance. We show numerically that our algorithm is the fastest known for problems over bounded disjunction languages for some values of k <= 500 and we look at the branching time temporal language, which is a bounded disjunction language, to show how to transform a specific problem to (d,k)-ClSP. We also look at Allen's interval algebra but conclude that there is already a faster algorithm for solving this problem.

Place, publisher, year, edition, pages
2017. , p. 44
Keywords [en]
CSP, Algorithms
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-141600ISRN: LIU-IDA/LITH-EX-A--17/046--SEOAI: oai:DiVA.org:liu-141600DiVA, id: diva2:1146285
Subject / course
Computer science
Supervisors
Examiners
Available from: 2017-10-03 Created: 2017-10-02 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

fulltext(427 kB)71 downloads
File information
File name FULLTEXT01.pdfFile size 427 kBChecksum SHA-512
161ee7e5044e8e89b54b2cfbeef351acaf8c84263b19764c3bb0a7e93a8dc30a5ff8fde61a1ac543bb755183072c8af6f4c66c60a5a5c58143acdab34b7e6425
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Einarson, Carl
By organisation
Software and Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 71 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

urn-nbn

Altmetric score

urn-nbn
Total: 1814 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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