Grant: Discovery Grants Program - Individual
University of Western Ontario
$24,000.00
Approximation algorithms for packing and network problems
EF 2012-13
Résumé
A large number of practical optimization problems belong to the class NP-hard and, unfortunately, there is strong theoretical evidence suggesting that optimum solutions for NP-hard problems cannot be computed efficiently. Approximation algorithms are fundamental tools for dealing with this class of problems, as these algorithms can efficiently produce solutions that are guaranteed to be at most some factor c away from the optimum. Thus, a natural goal when designing approximation algorithms is to make this factor c as close to 1 as possible. In this research we are mainly interested in studying approximation algorithms for NP-hard optimization problems of two classes: packing and network problems. Networks are one of the most fundamental modeling tools in optimization, with applications to a large number of fields. Packing problems are of great importance in transportation, VLSI design, scheduling, and any other area requiring the arrangement of objects in bounded spaces.
The objectives of the research are
- The design of new techniques and the improvement of existing ones for designing efficient approximation
algorithms that produce provably near-optimum solutions for packing and network problems.
- The creation of algorithmic techniques for designing approximation algorithms that can use only a
pre-specified amount of time to try to produce the best possible approximate solutions for packing and
network problems.
- The development of analysis techniques to accurately bound the quality of solutions computed by
approximation algorithms.
- The development of techniques that can be used to experimentally estimate the accuracy of approximation
algorithms for optimization problems and for improving their average running times.
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
227829-2009
Name nom
SolisOba, Roberto
Department département
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
2012
Competition year année de concours
2009
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
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
4
Nb partie
5
Application title
Approximation algorithms for packing and network problems
Keyword
NSERC
Application summary
A large number of practical optimization problems belong to the class NP-hard and, unfortunately, there is strong theoretical evidence suggesting that optimum solutions for NP-hard problems cannot be computed efficiently. Approximation algorithms are fundamental tools for dealing with this class of problems, as these algorithms can efficiently produce solutions that are guaranteed to be at most some factor c away from the optimum. Thus, a natural goal when designing approximation algorithms is to make this factor c as close to 1 as possible. In this research we are mainly interested in studying approximation algorithms for NP-hard optimization problems of two classes: packing and network problems. Networks are one of the most fundamental modeling tools in optimization, with applications to a large number of fields. Packing problems are of great importance in transportation, VLSI design, scheduling, and any other area requiring the arrangement of objects in bounded spaces.
The objectives of the research are
- The design of new techniques and the improvement of existing ones for designing efficient approximation
algorithms that produce provably near-optimum solutions for packing and network problems.
- The creation of algorithmic techniques for designing approximation algorithms that can use only a
pre-specified amount of time to try to produce the best possible approximate solutions for packing and
network problems.
- The development of analysis techniques to accurately bound the quality of solutions computed by
approximation algorithms.
- The development of techniques that can be used to experimentally estimate the accuracy of approximation
algorithms for optimization problems and for improving their average running times.