Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Alberta

$24,000.00

Approximation algorithms, approximablity, and algorithmic graph theory

FY 2012-13

Summary
My current and planned research focuses on the following sub-areas in theoretical computer science: i) design of efficient approximation algorithms for problems that naturally arise in applications such as network design and computational economy, (ii) study of computational complexity and hardness of approximation for such problem, and (iii) algorithmic aspects of graph theory and graph coloring problems on planar graphs. Most of the real world optimization problems, such as the ones on graphs that arise from applications in the design of networks, are NP-hard. Therefore, under widely believed assumptions, we cannot solve these problems in a reasonable amount of time. Given this, it is typically acceptable to compute a near optimal solution efficiently. So research has focused on the study of approximation algorithms; these are algorithms that run fast and produce a solution that is within a guaranteed factor of the optimal one. Among these optimization problems, those related to graphs and network design are particularly important and have attracted more attention recently. Another class of such problems arise in computational economy (for example how to price bundles of items to maximize revenue and or customer satisfaction). It is also important to study the hardness of approximation (computational complexity) of these problems. This helps to put the quality of the proposed algorithms in perspective, and have a better understanding of the level of difficulty of these problems which in turn could be used to design better algorithms. A significant amount of my research will involve the study of coloring and other problems on graphs and in particular on planar graphs. Some of these problems (which have theoretical importance) have also applications in frequency channel assignments in a cellular network. The question of minimizing the number of colors in a specific coloring problem translates to minimizing the frequency bandwidth required in such a network.
Program
Discovery Grants Program - Individual
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
311704-2008
Name nom
Salavatipour, MohammadReza
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
2012
Competition year année de concours
2008
Award amount
24000
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
5
Nb partie
5
Application title
Approximation algorithms, approximablity, and algorithmic graph theory
Keyword
NSERC
Application summary
My current and planned research focuses on the following sub-areas in theoretical computer science: i) design of efficient approximation algorithms for problems that naturally arise in applications such as network design and computational economy, (ii) study of computational complexity and hardness of approximation for such problem, and (iii) algorithmic aspects of graph theory and graph coloring problems on planar graphs. Most of the real world optimization problems, such as the ones on graphs that arise from applications in the design of networks, are NP-hard. Therefore, under widely believed assumptions, we cannot solve these problems in a reasonable amount of time. Given this, it is typically acceptable to compute a near optimal solution efficiently. So research has focused on the study of approximation algorithms; these are algorithms that run fast and produce a solution that is within a guaranteed factor of the optimal one. Among these optimization problems, those related to graphs and network design are particularly important and have attracted more attention recently. Another class of such problems arise in computational economy (for example how to price bundles of items to maximize revenue and or customer satisfaction). It is also important to study the hardness of approximation (computational complexity) of these problems. This helps to put the quality of the proposed algorithms in perspective, and have a better understanding of the level of difficulty of these problems which in turn could be used to design better algorithms. A significant amount of my research will involve the study of coloring and other problems on graphs and in particular on planar graphs. Some of these problems (which have theoretical importance) have also applications in frequency channel assignments in a cellular network. The question of minimizing the number of colors in a specific coloring problem translates to minimizing the frequency bandwidth required in such a network.