Grant: Discovery Grants Program - Individual
University of British Columbia
$18,000.00
Algorithms, heuristics and typical case complexity of hard problems
EF 2006-07
Résumé
During the past decade there has been an extensive study of the phase transition phenomena in various combinatorial search problems such as Propositional Satisfiability (SAT), Constraint Satisfaction Problem (CSP), and graph coloring. These problems are computationally hard in the worst-case, but are of great importance in artificial intelligence and other application domains such as planning, scheduling, and communication networks. The growing interest in the study of the phase transitions in combinatorial search is due to the observation that the typical-case hardness of a random instance is closely related to the phase transition of the solution probability under some instance distribution. Far from the threshold, random instances are typically under-constrained (or over-constrained) and are very easy to solve. Around the threshold, however, extremely hard instances tend to appear with high probability. In the proposed research program, we study theoretically and empirically the interplays among the efficiency of heuristics in search algorithms, the typical-case complexity of problem instances randomly-generated from certain probability distributions, and the various problem structures such as problem representation (encoding), constraint consistency, backbones, backdoors, and structural symmetry. The objectives are (1) to gain insight on the impact of problem structures on the performance of different heuristics and to draw guidance regarding the design of efficient heuristics; (2) to understand the fundamental limitations of different classes of search algorithms; and (3) to develop algorithmic solutions to real-world problems. The algorithmic problems to be investigated fall into three categories: (A) Traditional NP-complete problems that are of interests in artificial intelligence; (B) Specific problems in graph theory with special properties such as the dominating clique problem and the tree-width problem; and (C) Problems from application domains such as the phylogeny reconstruction problem and the multi-constrained path problem in communication networks.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
327587-2006
Name nom
Gao, Yong
Department département
Computer Science
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2006
Competition year année de concours
2006
Award amount
18000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Partie
1
Nb partie
3
Application title
Algorithms, heuristics and typical case complexity of hard problems
Keyword
NA
Application summary
During the past decade there has been an extensive study of the phase transition phenomena in various combinatorial search problems such as Propositional Satisfiability (SAT), Constraint Satisfaction Problem (CSP), and graph coloring. These problems are computationally hard in the worst-case, but are of great importance in artificial intelligence and other application domains such as planning, scheduling, and communication networks. The growing interest in the study of the phase transitions in combinatorial search is due to the observation that the typical-case hardness of a random instance is closely related to the phase transition of the solution probability under some instance distribution. Far from the threshold, random instances are typically under-constrained (or over-constrained) and are very easy to solve. Around the threshold, however, extremely hard instances tend to appear with high probability. In the proposed research program, we study theoretically and empirically the interplays among the efficiency of heuristics in search algorithms, the typical-case complexity of problem instances randomly-generated from certain probability distributions, and the various problem structures such as problem representation (encoding), constraint consistency, backbones, backdoors, and structural symmetry. The objectives are (1) to gain insight on the impact of problem structures on the performance of different heuristics and to draw guidance regarding the design of efficient heuristics; (2) to understand the fundamental limitations of different classes of search algorithms; and (3) to develop algorithmic solutions to real-world problems. The algorithmic problems to be investigated fall into three categories: (A) Traditional NP-complete problems that are of interests in artificial intelligence; (B) Specific problems in graph theory with special properties such as the dominating clique problem and the tree-width problem; and (C) Problems from application domains such as the phylogeny reconstruction problem and the multi-constrained path problem in communication networks.