Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$43,000.00

Algorithms and complexity of the constraint satisfaction problem

FY 2014-15

Summary
The aim in a constraint satisfaction problem (CSP) is to find an assignment of values to a given set of variables, subject to constraints on the values which can be assigned simultaneously to certain specified subsets of variables. In its counting version (#CSP) the goal is to find or approximate the number of such assignments. CSP and #CSP can be used to model a wide variety of computational problems in computer science, discrete mathematics, artificial intelligence, and elsewhere, they have found numerous applications in those areas. As the general CSP is NP-complete (and #CSP is NP-hard), and therefore it is unlikely that there is an efficient general algorithm for these problems, a major research direction in these problems is to determine the complexity of certain restricted problems of this type. Several very successful approaches to tackle this goal have been developed over the past 5-7 years. One of the most fruitful ones has been the algebraic one. The overall objectives of the present proposal include: (1) Determine the exact complexity of restricted CSPs. (2) Study the complexity and approximation complexity of the weighted #CSP. Progress in (1) will lead to designing new efficient algorithms for the CSP and better understanding of such problems. It also has assisted and will assist in related fields such as graph colorings and homomorphisms, universal algebra, and certain areas of logic. In (2) the weighted #CSP generalizes the standard #CSP and includes, in particular, such problems as computing partition functions that appear in statistical physics and elsewhere. Recent results show that weighted CSPs with rational weights are equivalent to the standard #CSP, and therefore the algebraic approach can be used in this case. Since efficient exact algorithms for #CSP exist only for a very restricted type of constraints, approximation algorithms become especially important as a more practical tool for solving such problems.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
313357-2010
Name nom
Bulatov, Andrei
Department département
Computing Science, School of
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2010
Award amount
43000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
5
Nb partie
5
Application title
Algorithms and complexity of the constraint satisfaction problem
Keyword
NSERC
Application summary
The aim in a constraint satisfaction problem (CSP) is to find an assignment of values to a given set of variables, subject to constraints on the values which can be assigned simultaneously to certain specified subsets of variables. In its counting version (#CSP) the goal is to find or approximate the number of such assignments. CSP and #CSP can be used to model a wide variety of computational problems in computer science, discrete mathematics, artificial intelligence, and elsewhere, they have found numerous applications in those areas. As the general CSP is NP-complete (and #CSP is NP-hard), and therefore it is unlikely that there is an efficient general algorithm for these problems, a major research direction in these problems is to determine the complexity of certain restricted problems of this type. Several very successful approaches to tackle this goal have been developed over the past 5-7 years. One of the most fruitful ones has been the algebraic one. The overall objectives of the present proposal include: (1) Determine the exact complexity of restricted CSPs. (2) Study the complexity and approximation complexity of the weighted #CSP. Progress in (1) will lead to designing new efficient algorithms for the CSP and better understanding of such problems. It also has assisted and will assist in related fields such as graph colorings and homomorphisms, universal algebra, and certain areas of logic. In (2) the weighted #CSP generalizes the standard #CSP and includes, in particular, such problems as computing partition functions that appear in statistical physics and elsewhere. Recent results show that weighted CSPs with rational weights are equivalent to the standard #CSP, and therefore the algebraic approach can be used in this case. Since efficient exact algorithms for #CSP exist only for a very restricted type of constraints, approximation algorithms become especially important as a more practical tool for solving such problems.
Simon Fraser University - $43,000 Grant (2014-15) | Canada Spends