Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$74,000.00

Design and analysis of algorithms, mathematics of information retrieval, complexity theory

EF 2010-11

Résumé
This proposal primarily concerns a number of topics relating to the design and analysis of algorithms incluing potential application to the areas of information retrieval, algorithmic mechanism design and bio- informatics. My current focus is on the design and analysis of ""simple"" and efficient classes of algorithms, such as greedy algorithms, local search, dynamic programming and local ratio/primal dual algorithms. These general techniques are the starting point (and sometimes the most efficient algorithms known) for many combinatorial optimization and search problems. While the meaning of such algorithmic paradigms is intuitively understood, establishing a precise and ""useful"" model of such algorithms is a challenging area of research. We consider precise models which capture known algorithms but moreover allow us to prove limitations on a particular approach as well as possibly suggesting ideas for deriving new algorithms.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
7631-2007
Name nom
Borodin, Allan
Department département
Computer Science
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2007
Award amount
74000
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
802
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
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
4
Nb partie
5
Application title
Design and analysis of algorithms, mathematics of information retrieval, complexity theory
Keyword
NSERC
Application summary
This proposal primarily concerns a number of topics relating to the design and analysis of algorithms incluing potential application to the areas of information retrieval, algorithmic mechanism design and bio- informatics. My current focus is on the design and analysis of ""simple"" and efficient classes of algorithms, such as greedy algorithms, local search, dynamic programming and local ratio/primal dual algorithms. These general techniques are the starting point (and sometimes the most efficient algorithms known) for many combinatorial optimization and search problems. While the meaning of such algorithmic paradigms is intuitively understood, establishing a precise and ""useful"" model of such algorithms is a challenging area of research. We consider precise models which capture known algorithms but moreover allow us to prove limitations on a particular approach as well as possibly suggesting ideas for deriving new algorithms.