Grant: Discovery Grants Program - Individual
The University of Western Ontario
$24,000.00
Approximation Algorithms for Combinatorial Optimization Problems
EF 2023-24
Résumé
Many optimization problems in manufacturing, transportation, communications, finances, and many other fields require solutions that optimize the use of available resources. An important class of these problems are combinatorial optimization problems. Many of these problems are too complex to solve without the use of computers and, hence, efficient computer algorithms for solving them are needed. However, there is strong theoretical evidence suggesting that even modern fast computers are not powerful enough to efficiently solve many of these optimization problems; these problems get the technical name of NP-hard. Despite the seeming impossibility for solving NP-hard problems efficiently (or,technically, in polynomial time), we still need to deal with them since they arise in industrial and commercial applications. One important tool for dealing with these problems is approximation algorithms; these are efficient algorithms that yield solutions whose values are within some factor c from the optimum. Knowing how close to optimal are the solutions produced by approximation algorithms helps us determine how well we can solve complex problems of practical relevance. This research focuses on the design of approximation algorithms for three kinds of problems: network, scheduling and packing problems. Networks are one of the most fundamental modelling tools in optimization and scheduling and packing problems are of great importance in domains requiring the effective management of limited resources. Goals: 1. To design efficient approximation algorithms that exploit the special structure of restricted instances of scheduling, packing, and network optimization problems that arise in practical applications. The inherent nature of practical applications many times restricts the set of inputs that my appear in instances of optimization problems arising from them. I plan to work on exploiting the structure of these restricted instances to discover good design techniques for them. 2. To formulate new techniques for the design of approximation algorithms for scheduling, packing, and network problems that yield approximation algorithms with practical running times. I will work on extending and combining existing design techniques for approximation algorithms so they are applicable to a larger set of problems. 3. To study the trade-off between the quality of solutions produced by approximation algorithms and their running times. In practical applications it is necessary to limit the amount of time that an algorithm can run. I plan to work on understanding what is the best solution that one can hope to obtain for a particular problem within a given amount of time. I expect my research to lead to approximation algorithms that are better suited than existing ones for practical applications of network, scheduling and packing problems, both with respect to approximation ratio and running time. This research is of theoretical and practical importance.
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
RGPIN-2020-06423
Name nom
Solis-Oba, Roberto
Department département
Computer Science - Computer Science
Organization id
36
Institution établissement
The University of Western Ontario
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2020
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 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
801
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
Computer software
Area of application fr
Logiciel
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Optimization
Research subject en
Technologie de l'information
Research subject fr
Optimisation
Application title
Approximation Algorithms for Combinatorial Optimization Problems
Keyword
Approximation algorithms; Combinatorial optimization; Complexity; Efficient algorithms; Networks; NP hard; Packing problems; Scheduling problems
Application summary
Many optimization problems in manufacturing, transportation, communications, finances, and many other fields require solutions that optimize the use of available resources. An important class of these problems are combinatorial optimization problems. Many of these problems are too complex to solve without the use of computers and, hence, efficient computer algorithms for solving them are needed. However, there is strong theoretical evidence suggesting that even modern fast computers are not powerful enough to efficiently solve many of these optimization problems; these problems get the technical name of NP-hard. Despite the seeming impossibility for solving NP-hard problems efficiently (or,technically, in polynomial time), we still need to deal with them since they arise in industrial and commercial applications. One important tool for dealing with these problems is approximation algorithms; these are efficient algorithms that yield solutions whose values are within some factor c from the optimum. Knowing how close to optimal are the solutions produced by approximation algorithms helps us determine how well we can solve complex problems of practical relevance. This research focuses on the design of approximation algorithms for three kinds of problems: network, scheduling and packing problems. Networks are one of the most fundamental modelling tools in optimization and scheduling and packing problems are of great importance in domains requiring the effective management of limited resources. Goals: 1. To design efficient approximation algorithms that exploit the special structure of restricted instances of scheduling, packing, and network optimization problems that arise in practical applications. The inherent nature of practical applications many times restricts the set of inputs that my appear in instances of optimization problems arising from them. I plan to work on exploiting the structure of these restricted instances to discover good design techniques for them. 2. To formulate new techniques for the design of approximation algorithms for scheduling, packing, and network problems that yield approximation algorithms with practical running times. I will work on extending and combining existing design techniques for approximation algorithms so they are applicable to a larger set of problems. 3. To study the trade-off between the quality of solutions produced by approximation algorithms and their running times. In practical applications it is necessary to limit the amount of time that an algorithm can run. I plan to work on understanding what is the best solution that one can hope to obtain for a particular problem within a given amount of time. I expect my research to lead to approximation algorithms that are better suited than existing ones for practical applications of network, scheduling and packing problems, both with respect to approximation ratio and running time. This research is of theoretical and practical importance.