Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$41,000.00

Feasible special cases of computationally difficult problems

EF 2010-11

Résumé
My work deals with problems that are abstractions of tasks that need to be carried out in the real world -- for example, finding a conflict-free schedule for student exams, or locating drop boxes to minimize the amount of walking that letter carriers must do. Many such problems appear to be inherently hard, in that small instances can be solved by exhaustively trying all possibilities, but there are no good methods known for large instances. We have mathematical evidence that there may be no good methods for these problems, but they still need to be solved in practice. One hope is that these problems may have natural parameters which are small for many instances (perhaps the number of exam rooms, or the number of boxes the post office is willing to install) and for small parameters we can find good methods of solution. Such methods are known as fixed-parameter tractable (FPT) algorithms. I try to find FPT algorithms for problems. Some of these problems are defined on basic mathematical structures that are useful in many different contexts. Other work arises from particular areas of application, for example, the visual layout of information such as an organizational chart, or inferring an evolutionary tree from similarity information about present-day species. For some of these problems, I look for FPT algorithms, and for others, I look for mathematical evidence that even for small parameters there are no good solutions. This work should be considered basic research which not only has the potential for practical application but, in its emphasis on provable correctness and analyzable efficiency, is excellent training for students.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
41913-2008
Name nom
Ragde, Prabhakar
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2008
Award amount
41000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
3
Nb partie
5
Application title
Feasible special cases of computationally difficult problems
Keyword
NSERC
Application summary
My work deals with problems that are abstractions of tasks that need to be carried out in the real world -- for example, finding a conflict-free schedule for student exams, or locating drop boxes to minimize the amount of walking that letter carriers must do. Many such problems appear to be inherently hard, in that small instances can be solved by exhaustively trying all possibilities, but there are no good methods known for large instances. We have mathematical evidence that there may be no good methods for these problems, but they still need to be solved in practice. One hope is that these problems may have natural parameters which are small for many instances (perhaps the number of exam rooms, or the number of boxes the post office is willing to install) and for small parameters we can find good methods of solution. Such methods are known as fixed-parameter tractable (FPT) algorithms. I try to find FPT algorithms for problems. Some of these problems are defined on basic mathematical structures that are useful in many different contexts. Other work arises from particular areas of application, for example, the visual layout of information such as an organizational chart, or inferring an evolutionary tree from similarity information about present-day species. For some of these problems, I look for FPT algorithms, and for others, I look for mathematical evidence that even for small parameters there are no good solutions. This work should be considered basic research which not only has the potential for practical application but, in its emphasis on provable correctness and analyzable efficiency, is excellent training for students.