Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Alberta

$48,000.00

Approximation Algorithms for Applied Optimization Problems

EF 2024-25

Résumé
Theoretical Computer Science is a diverse area. Research in theoretical computer science can span various sub-areas, but the ones considered here are inspired by real world applications. Typically these are optimization problems initiated from some application and there is a need to first formulate the problem mathematically in which we wish to optimize some objective function (e.g. cost, time, v.s. quality of service, profit). Then the next step is to develop an algorithm for the problem backed by a rigorous analysis of its performance and correctness. Since most of these problems are NP-hard, unless P \not= NP, we cannot determine their optimal solution efficiently. Therefore, a line of research has emerged with focus on the study of approximation algorithms. These are algorithms that run fast (typically polynomial time) and produce solutions that are guaranteed to be within some proven factor of the optimal solution. Perhaps one of the important motivating factors of study of these types of 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 very practical. Note that, although the worst performance ratio obtained in the analysis might seem quite bad, in many situation the actual performance in reality is much better. It is also important to study hardness of approximation, i.e. prove lower bounds on approximability of problems. This study often yields a deeper understanding of the spectrum of the NP-hard optimization problems we have and can be used to develop new and better approximation algorithms. Some of the major topics that I have explored include: design and analysis of approximation algorithms, Stochastic Optimization problems, and approximation algorithms equipped with predictions (e.g. provided by ML), More specifically, over the next few years I plan to focus on the study of some clustering problems (these include generalization of classical problems such as k-Median/k-Means or Facility Location), vehicle routing and orienteering problems (such as Capacitated Vehicle Routing, Deadline Orienteering, and stochastic versions), and design of approximation algorithms for various optimization problems when the algorithm is provided with stochastic information or predictions (perhaps provided by a ML algorithm) about the instance properties in advance and/or the form of a potential good solution.  This is a relatively new line of research that has drawn much attraction given the possibility of use of Machine Learning in providing some prediction of data and or potential solution. The hope is to design better approximation algorithms for these problems (with provable bounds on the quality of the solution) in general settings and/or in some special cases that often appear in applications.
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
RGPIN-2024-05096
Name nom
Salavatipour, Mohammad
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
2024
Competition year année de concours
2024
Award amount
48000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Approximation Algorithms for Applied Optimization Problems
Keywords
approximation algorithms; combinatorial optimization; clustering and facility location; network design; vehicle routing; scheduling and resource allocation; hardness of approximation; algorithms with prediction
Application summary
Theoretical Computer Science is a diverse area. Research in theoretical computer science can span various sub-areas, but the ones considered here are inspired by real world applications. Typically these are optimization problems initiated from some application and there is a need to first formulate the problem mathematically in which we wish to optimize some objective function (e.g. cost, time, v.s. quality of service, profit). Then the next step is to develop an algorithm for the problem backed by a rigorous analysis of its performance and correctness. Since most of these problems are NP-hard, unless P \not= NP, we cannot determine their optimal solution efficiently. Therefore, a line of research has emerged with focus on the study of approximation algorithms. These are algorithms that run fast (typically polynomial time) and produce solutions that are guaranteed to be within some proven factor of the optimal solution. Perhaps one of the important motivating factors of study of these types of 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 very practical. Note that, although the worst performance ratio obtained in the analysis might seem quite bad, in many situation the actual performance in reality is much better. It is also important to study hardness of approximation, i.e. prove lower bounds on approximability of problems. This study often yields a deeper understanding of the spectrum of the NP-hard optimization problems we have and can be used to develop new and better approximation algorithms. Some of the major topics that I have explored include: design and analysis of approximation algorithms, Stochastic Optimization problems, and approximation algorithms equipped with predictions (e.g. provided by ML), More specifically, over the next few years I plan to focus on the study of some clustering problems (these include generalization of classical problems such as k-Median/k-Means or Facility Location), vehicle routing and orienteering problems (such as Capacitated Vehicle Routing, Deadline Orienteering, and stochastic versions), and design of approximation algorithms for various optimization problems when the algorithm is provided with stochastic information or predictions (perhaps provided by a ML algorithm) about the instance properties in advance and/or the form of a potential good solution.  This is a relatively new line of research that has drawn much attraction given the possibility of use of Machine Learning in providing some prediction of data and or potential solution. The hope is to design better approximation algorithms for these problems (with provable bounds on the quality of the solution) in general settings and/or in some special cases that often appear in applications.