Grant: Discovery Grants Program - Individual
University of Victoria
$24,000.00
Computational problems & tractable algorithms: Bridging the gap between problem definitions and solutions
EF 2011-12
Résumé
Complexity theory provides us with tools to understand how difficult a computational problem is. Classical complexity distinguishes between problems that are solvable in polynomial time (P), and problems that are intractable (NP-hard) and likely not in P. The list of NP-hard problems is long. Parameterized complexity takes a refined view on intractable problems. It distinguishes between problems that are fixed-parameter tractable (fpt) for a chosen parameter and problems that likely do not have this property. Running times of fpt algorithms are not in P but can be tractable as long as parameter values are not too large. We investigate the tractability of problems in the areas of bioinformatics, data anonymization and cognitive science. In bioinformatics we are interested in sequence analysis problems. In this area, we consider two types of intractability: NP-hardness and large input sizes. For both we develop tractable exact algorithms, the former using methods from parameterized complexity, the latter using external memory methods. Exact algorithms help biologists evaluate their models used to analyze data. In data anonymization, we investigate data sets that are to be processed to make the sources unidentifiable while modifying the original data as little as possible. Data anonymization problems are important in our technological and internet-oriented world; the ability to anonymize data quickly is highly relevant. Many are NP-hard and often only inexact methods, if any, exist in practice. Our objective is to devise fpt algorithms for solving these problems. In cognitive science one goal is to understand what problems (cognitive theories) humans tackle in decision making and what methods they apply to solve them. It has been observed that humans tend to be good in solving instances of some hard computational problems. The use of exact algorithms in industry will improve the quality of industrial algorithms. Optimality guarantees of the solutions will improve the quality of the evaluation of data in academia and industry. The research findings in cognitive modeling will significantly impact the ability of cognitive psychologists to identify new theories.
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
249898-2011
Name nom
Stege, Ulrike
Department département
Computer Science
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2011
Award amount
24000
Program id
RGPIN
Program nane 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
1201
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Life sciences (including biotechnology)
Area of application fr
Sciences de la vie (y compris biotechnologie)
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
1
Nb partie
5
Application title
Computational problems & tractable algorithms: Bridging the gap between problem definitions and solutions
Keyword
NSERC
Application summary
Complexity theory provides us with tools to understand how difficult a computational problem is. Classical complexity distinguishes between problems that are solvable in polynomial time (P), and problems that are intractable (NP-hard) and likely not in P. The list of NP-hard problems is long. Parameterized complexity takes a refined view on intractable problems. It distinguishes between problems that are fixed-parameter tractable (fpt) for a chosen parameter and problems that likely do not have this property. Running times of fpt algorithms are not in P but can be tractable as long as parameter values are not too large. We investigate the tractability of problems in the areas of bioinformatics, data anonymization and cognitive science. In bioinformatics we are interested in sequence analysis problems. In this area, we consider two types of intractability: NP-hardness and large input sizes. For both we develop tractable exact algorithms, the former using methods from parameterized complexity, the latter using external memory methods. Exact algorithms help biologists evaluate their models used to analyze data. In data anonymization, we investigate data sets that are to be processed to make the sources unidentifiable while modifying the original data as little as possible. Data anonymization problems are important in our technological and internet-oriented world; the ability to anonymize data quickly is highly relevant. Many are NP-hard and often only inexact methods, if any, exist in practice. Our objective is to devise fpt algorithms for solving these problems. In cognitive science one goal is to understand what problems (cognitive theories) humans tackle in decision making and what methods they apply to solve them. It has been observed that humans tend to be good in solving instances of some hard computational problems. The use of exact algorithms in industry will improve the quality of industrial algorithms. Optimality guarantees of the solutions will improve the quality of the evaluation of data in academia and industry. The research findings in cognitive modeling will significantly impact the ability of cognitive psychologists to identify new theories.