liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Upper and Lower Bounds on the Time Complexity of Infinite-domain CSPs
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. (TCSLAB)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. (TCSLAB)
2015 (English)In: Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015, Proceedings, Springer Berlin/Heidelberg, 2015, Vol. 9255, 183-199 p.Conference paper (Refereed)
Abstract [en]

The constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science. For infinite-domain CSPs, there are many results separating tractable and NP-hard cases while upper bounds on the time complexity of hard cases are virtually unexplored. Hence, we initiate a study of the worst-case time cmplexity of such CSPs. We analyse backtracking algorithms and show that they can be improved by exploiting sparsification. We present even faster algorithms based on enumerating finite structures. Last, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that the strong exponential-time hypothesis is true.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015. Vol. 9255, 183-199 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 9255
National Category
Computer and Information Science Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-123120DOI: 10.1007/978-3-319-23219-5_14ISI: 000364707100014ISBN: 978-3-319-23218-8OAI: oai:DiVA.org:liu-123120DiVA: diva2:876689
Conference
21st International Conference on Principles and Practice of Constraint Programming (CP-2015)
Available from: 2015-12-04 Created: 2015-12-04 Last updated: 2015-12-11

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, PeterLagerkvist, Victor
By organisation
Software and SystemsFaculty of Science & Engineering
Computer and Information ScienceComputer 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

Altmetric score

Total: 10 hits
ReferencesLink to record
Permanent link

Direct link