Grant: Discovery Grants Program - Individual
University of Alberta
$35,000.00
Discrete algorithmics with applications to combinatorial optimization
FY 2007-08
Summary
Many problems studied by computer scientists can be modelled by some discrete, as opposed to continuous, structure. For example, a graph is a mathematical object that can be drawn on a piece of paper by first drawing some dots and then drawing lines between some pairs of dots. The only relevant information in a graph is which dot pairs are joined by a line. Many kinds of problems can be modelled with graphs, including communication problems (e.g. routing calls through a phone network), transportation problems (e.g. routing delivery vehicles), location problems (e.g. finding the location of a gene in the human genome sequence). In many of these problems some aspect requires optimization. For example, with delivery vehicles travel time should be minimized; with gene location the number of matched gene sites should be maximized. Algorithms which find optimized solutions efficiently are desired. Understanding the underlying discrete structure of these problems often leads to efficient algorithms. Once these properties are understood, efficient optimization algorithms can be designed. This proposal concerns certain kinds of graphs for which some optimization problems can be solved very efficiently, and the algorithms associated with those optimization problems.
Program
Discovery Grants Program - Individual
Recipient
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
137764-2006
Name nom
Hayward, Ryan
Department département
Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2007
Competition year année de concours
2006
Award amount
35000
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
Discrete algorithmics with applications to combinatorial optimization
Keyword
NA
Application summary
Many problems studied by computer scientists can be modelled by some discrete, as opposed to continuous, structure. For example, a graph is a mathematical object that can be drawn on a piece of paper by first drawing some dots and then drawing lines between some pairs of dots. The only relevant information in a graph is which dot pairs are joined by a line. Many kinds of problems can be modelled with graphs, including communication problems (e.g. routing calls through a phone network), transportation problems (e.g. routing delivery vehicles), location problems (e.g. finding the location of a gene in the human genome sequence). In many of these problems some aspect requires optimization. For example, with delivery vehicles travel time should be minimized; with gene location the number of matched gene sites should be maximized. Algorithms which find optimized solutions efficiently are desired. Understanding the underlying discrete structure of these problems often leads to efficient algorithms. Once these properties are understood, efficient optimization algorithms can be designed. This proposal concerns certain kinds of graphs for which some optimization problems can be solved very efficiently, and the algorithms associated with those optimization problems.