Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of British Columbia

$50,000.00

Computational complexity of geometric and combinatorial problems

EF 2010-11

Résumé
The objective of the proposed research is to further our understanding of the inherent computational complexity of a number of fundamental combinatorial and geometric problems. Our main goal is to provide answers to two complementary questions: (i) ""In what ways and to what extent do certain structural features (attributes of specific problem instances) contribute to the difficulty of solving problems in a particular family?"" and (ii) ""In what ways and to what extent can certain naturally occurring features or constraints be exploited to provide more efficient solutions for problem instances that exhibit these features?"" The problems that we propose to address (like those addressed in my previous research) are distinguished by the fundamental role that they play in a variety of applications, including robotic motion planning and optimization, facility and sensor location, efficient schemes for broadcasting streamed information and optimization of log milling. This, of course, provides significant practical motivation for progress on the second of the questions above. However, the problems are also chosen for their ability to serve as representatives of broader families of similarly structured problems. For this reason they motivate, from a more theoretical standpoint, progress on the first question. Ultimately, our success should be measured in terms of (i) the development of new general techniques for the design and analysis of efficient algorithms and data structures, and (ii) the elucidation of inherent complexity limitations that apply in the broadest possible computational context.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
3583-2009
Name nom
Kirkpatrick, David
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
2010
Competition year année de concours
2009
Award amount
50000
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Computational complexity of geometric and combinatorial problems
Keyword
NSERC
Application summary
The objective of the proposed research is to further our understanding of the inherent computational complexity of a number of fundamental combinatorial and geometric problems. Our main goal is to provide answers to two complementary questions: (i) ""In what ways and to what extent do certain structural features (attributes of specific problem instances) contribute to the difficulty of solving problems in a particular family?"" and (ii) ""In what ways and to what extent can certain naturally occurring features or constraints be exploited to provide more efficient solutions for problem instances that exhibit these features?"" The problems that we propose to address (like those addressed in my previous research) are distinguished by the fundamental role that they play in a variety of applications, including robotic motion planning and optimization, facility and sensor location, efficient schemes for broadcasting streamed information and optimization of log milling. This, of course, provides significant practical motivation for progress on the second of the questions above. However, the problems are also chosen for their ability to serve as representatives of broader families of similarly structured problems. For this reason they motivate, from a more theoretical standpoint, progress on the first question. Ultimately, our success should be measured in terms of (i) the development of new general techniques for the design and analysis of efficient algorithms and data structures, and (ii) the elucidation of inherent complexity limitations that apply in the broadest possible computational context.