Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Lethbridge

$19,000.00

Linear programming based approximation algorithms for optimization problems

FY 2009-10

Summary
Approximation algorithms are an elegant formal framework for dealing with intrinsically hard optimization problems. An approximation algorithm for an optimization problem produces a feasible solution in polynomial time that is within a constant multiplicative factor of the optimal solution for every instance of the problem. Approximation ratio is only a worst-case bound and pathological instances are usually hard to find. It has been experimentally observed for a variety of approximation algorithms that, on average, the performance is vastly superior than the stated bound. An approximation algorithm can always be refined and tuned to specific classes of instances arising in practice, thereby improving the performance. I am studying approximation algorithm design based on linear and semi-definite programming techniques. Quality or the integrality gap of the relaxation, techniques used to round the fractional solutions to the integer solutions, and the time needed to compute the optimal solution to the relaxations, all effect the quality of the approximation. My research focusses on improvements on these fronts and it will lead to improved techniques and approximation algorithms for optimization problems.
Program
Discovery Grants Program - Individual
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
262126-2009
Name nom
Gaur, Daya
Department département
Mathematics and Computer Science
Organization id
12
Institution établissement
University of Lethbridge
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2009
Award amount
19000
Program id
RGPIN
Program nane 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
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Partie
1
Nb partie
5
Application title
Linear programming based approximation algorithms for optimization problems
Keyword
NA
Application summary
Approximation algorithms are an elegant formal framework for dealing with intrinsically hard optimization problems. An approximation algorithm for an optimization problem produces a feasible solution in polynomial time that is within a constant multiplicative factor of the optimal solution for every instance of the problem. Approximation ratio is only a worst-case bound and pathological instances are usually hard to find. It has been experimentally observed for a variety of approximation algorithms that, on average, the performance is vastly superior than the stated bound. An approximation algorithm can always be refined and tuned to specific classes of instances arising in practice, thereby improving the performance. I am studying approximation algorithm design based on linear and semi-definite programming techniques. Quality or the integrality gap of the relaxation, techniques used to round the fractional solutions to the integer solutions, and the time needed to compute the optimal solution to the relaxations, all effect the quality of the approximation. My research focusses on improvements on these fronts and it will lead to improved techniques and approximation algorithms for optimization problems.