Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Western Ontario

$18,000.00

Approximation algorithms for optimization problems

EF 2016-17

Résumé
Combinatorial optimization deals with finding optimum solutions for problems of a discrete and finite nature. Such problems arise in areas as diverse as Computer Science, Mathematics, Finances, Biology, Medicine, and Operations Research, among others. Many of these problems are too complex to solve without the use of computers and, therefore, efficient algorithms for solving them are needed. There is strong theoretical evidence suggesting that for many combinatorial optimization problems no polynomial time algorithm can compute exact solutions for them. Such problems get the technical name of NP-hard. One fundamental tool for dealing with these problems is approximation algorithms; these are efficient algorithms that yield solutions whose values can be proven to be no more than some factor c away from the optimum. My research interests center on the design of approximation algorithms. I am particularly interested in the study of approximation algorithms for two kinds of problems: Network and packing problems. Networks are one of the most fundamental modelling tools in optimization, with application to a large number of fields. Packing problems are of great importance in transportation, VLSI design, scheduling, and any other application domains requiring the arrangement of objects in bounded spaces. Within this research proposal we will pursue the following short term goals: - Investigate the combined use of local search and other optimization techniques in the design of approximation algorithms for facility location and clustering problems. - Design fixed parameter tractable approximation algorithms for packing and scheduling problems with restricted inputs. - Design efficient approximation algorithms for clustering problems in very large networks, like social networks. - Design effective experimental techniques for analyzing and improving the performance of approximation algorithms.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2015-04667
Name nom
SolisOba, Roberto
Department département
Computer Science - Computer Science
Organization id
36
Institution établissement
University of Western Ontario
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2015
Award amount
18000
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
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
Approximation algorithms for optimization problems
Keyword
NSERC
Application summary
Combinatorial optimization deals with finding optimum solutions for problems of a discrete and finite nature. Such problems arise in areas as diverse as Computer Science, Mathematics, Finances, Biology, Medicine, and Operations Research, among others. Many of these problems are too complex to solve without the use of computers and, therefore, efficient algorithms for solving them are needed. There is strong theoretical evidence suggesting that for many combinatorial optimization problems no polynomial time algorithm can compute exact solutions for them. Such problems get the technical name of NP-hard. One fundamental tool for dealing with these problems is approximation algorithms; these are efficient algorithms that yield solutions whose values can be proven to be no more than some factor c away from the optimum. My research interests center on the design of approximation algorithms. I am particularly interested in the study of approximation algorithms for two kinds of problems: Network and packing problems. Networks are one of the most fundamental modelling tools in optimization, with application to a large number of fields. Packing problems are of great importance in transportation, VLSI design, scheduling, and any other application domains requiring the arrangement of objects in bounded spaces. Within this research proposal we will pursue the following short term goals: - Investigate the combined use of local search and other optimization techniques in the design of approximation algorithms for facility location and clustering problems. - Design fixed parameter tractable approximation algorithms for packing and scheduling problems with restricted inputs. - Design efficient approximation algorithms for clustering problems in very large networks, like social networks. - Design effective experimental techniques for analyzing and improving the performance of approximation algorithms.