Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Alberta

$44,000.00

Approximation Algorithms and Hardness of Approximation for Optimization Problems

EF 2017-18

Résumé
My current and planned research focuses on design and analysis of efficient approximation algorithms for optimization problems that naturally arise in applications such as network design, scheduling, or computational economy. Most of the real world optimization problems, such as the ones in design of networks, are NP-hard. Therefore, under the assumption of ""P not equal to NP"", we cannot solve these problems optimally and efficiently (i.e. 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. Many of these algorithms are used in applications to attack these hard problems. Perhaps one of the important motivating factors of study of approximation algorithms is that often the techniques and algorithmic tools developed can be quite useful in other contexts, even if the approximation algorithm by itself may not be the best algorithm in practice. Among the hard optimization problems, those related to graphs and network design are particularly important and have drawn a lot of attention over the last few decades, and more so recently with the growing complications in the design of networks due to more sophisticated constraints. These problems include, more general minimum cost network flows, network connectivity with several constraints, and related cut problems, as well as some problems that arise from computational economy. It is also important to study hardness of approximation which is to prove lower bounds on approximability of the problems. This helps to put the quality of the proposed approximation algorithms in perspective and in turn could be used to design better algorithms. This line of research has been very active in the last two decades, specially since the development of Probabilistic Checkable Proof systems and the PCP theorem. I have successfully applied combinatorial and probabilistic techniques in the design and analysis of approximation algorithms as well as proving lower bounds for these problems and will continue to work in this area.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Alberta, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
311704-2013
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
2017
Competition year année de concours
2013
Award amount
44000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
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 and Hardness of Approximation for Optimization Problems
Keyword
NSERC
Application summary
My current and planned research focuses on design and analysis of efficient approximation algorithms for optimization problems that naturally arise in applications such as network design, scheduling, or computational economy. Most of the real world optimization problems, such as the ones in design of networks, are NP-hard. Therefore, under the assumption of ""P not equal to NP"", we cannot solve these problems optimally and efficiently (i.e. 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. Many of these algorithms are used in applications to attack these hard problems. Perhaps one of the important motivating factors of study of approximation algorithms is that often the techniques and algorithmic tools developed can be quite useful in other contexts, even if the approximation algorithm by itself may not be the best algorithm in practice. Among the hard optimization problems, those related to graphs and network design are particularly important and have drawn a lot of attention over the last few decades, and more so recently with the growing complications in the design of networks due to more sophisticated constraints. These problems include, more general minimum cost network flows, network connectivity with several constraints, and related cut problems, as well as some problems that arise from computational economy. It is also important to study hardness of approximation which is to prove lower bounds on approximability of the problems. This helps to put the quality of the proposed approximation algorithms in perspective and in turn could be used to design better algorithms. This line of research has been very active in the last two decades, specially since the development of Probabilistic Checkable Proof systems and the PCP theorem. I have successfully applied combinatorial and probabilistic techniques in the design and analysis of approximation algorithms as well as proving lower bounds for these problems and will continue to work in this area.