Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Lethbridge

$20,000.00

Approximation Algorithms for NP-hard Optimization Problems

EF 2017-18

Résumé
It is generally believed that efficient algorithms do not exist for finding an optimal solution to NP-hard opti-mization problems. A natural way to deal with the inability to find exact solutions efficiently is to trade thequality of solution for the computation time. Approximation algorithms do precisely that. Approximationalgorithms not only provide an approximate solution in polynomial time, they also provide a certificate ofoptimality for the solution. One can always refine and tune an approximation algorithm to specific class ofinstances arising in practice, thereby improving the performance ratio.Primary goal of this research is to further the theory and praxis of the design of approximation algorithms. Wewill design approximation algorithms for problems arising in the bioinformatics, facility location, schedul-ing, and machine learning domains. Our approach for designing approximation algorithms has theoreticalunderpinnings in combinatorial algorithms, linear and semi-definite programming. Linear programmingbased approaches have enjoyed a great deal of success in the recent past. The basic framework entails de-scribing the optimization problem as an integer linear program or a non-linear program over integer variables.A suitable linear programming relaxation or a semi-definite programming relaxation is constructed. The re-laxation is solved using efficient algorithms. A fractional solution thus obtained is converted to an integralsolution using some scheme. Care is taken to ensure that the process of converting the fractional solution toan integral solution does not increase the cost of the solution too much. Another approach is to simultane-ously construct an integral primal solution and candidate dual solution (possibly fractional) iteratively usingthe primal-dual schema. Primal-dual schema has the advantage that one can work with an exponential sizedformulation without having to resort to a separation oracle. Approaches based on the primal-dual schemahave been very successful for certain types of optimization problems. Integrality gap of an integer program-ming formulation is the gap in the cost of the optimal fractional and the cost of the optimal integral solution.Approximation algorithms based on linear or semi-definite programming have performance ratio no betterthan the integrality gap of the relaxation. Therefore integer programs with small integrality gap are criticalto the success of such approximation algorithms. The immediate program is i) to develop relaxations withbounded integrality gap for the optimization problems of interest or show none exists, ii) to develop combi-natorial algorithms for solving the relaxations where possible, and iii) to develop provably good strategiesfor converting the fractional solutions to the relaxations to integral solution. There has been considerableresearch activity on the hardness of approximations in the last few years and several deep results on the hard-ness of approximations have been obtained. The focus of this research is on the design of approximationalgorithms and we will draw on the results on hardness of approximations to guide the program.On the theoretical front we will push the frontier in approximation algorithms design. Research conducted aspart of this project will have prospect for commercialization and will be of immediate interest to the industry.Knowledge generated will be protected using patents (where applicable) and disseminated in high qualityjournals and conferences. The program will produce highly skilled manpower; skilled in the use of discreteoptimization theory and tools.
Programme
Discovery Grants Program - Individual
Emplacement
Alberta, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2014-06302
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
2017
Competition year année de concours
2014
Award amount
20000
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
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
Partie
4
Nb partie
5
Application title
Approximation Algorithms for NP-hard Optimization Problems
Keyword
NSERC
Application summary
It is generally believed that efficient algorithms do not exist for finding an optimal solution to NP-hard opti-mization problems. A natural way to deal with the inability to find exact solutions efficiently is to trade thequality of solution for the computation time. Approximation algorithms do precisely that. Approximationalgorithms not only provide an approximate solution in polynomial time, they also provide a certificate ofoptimality for the solution. One can always refine and tune an approximation algorithm to specific class ofinstances arising in practice, thereby improving the performance ratio.Primary goal of this research is to further the theory and praxis of the design of approximation algorithms. Wewill design approximation algorithms for problems arising in the bioinformatics, facility location, schedul-ing, and machine learning domains. Our approach for designing approximation algorithms has theoreticalunderpinnings in combinatorial algorithms, linear and semi-definite programming. Linear programmingbased approaches have enjoyed a great deal of success in the recent past. The basic framework entails de-scribing the optimization problem as an integer linear program or a non-linear program over integer variables.A suitable linear programming relaxation or a semi-definite programming relaxation is constructed. The re-laxation is solved using efficient algorithms. A fractional solution thus obtained is converted to an integralsolution using some scheme. Care is taken to ensure that the process of converting the fractional solution toan integral solution does not increase the cost of the solution too much. Another approach is to simultane-ously construct an integral primal solution and candidate dual solution (possibly fractional) iteratively usingthe primal-dual schema. Primal-dual schema has the advantage that one can work with an exponential sizedformulation without having to resort to a separation oracle. Approaches based on the primal-dual schemahave been very successful for certain types of optimization problems. Integrality gap of an integer program-ming formulation is the gap in the cost of the optimal fractional and the cost of the optimal integral solution.Approximation algorithms based on linear or semi-definite programming have performance ratio no betterthan the integrality gap of the relaxation. Therefore integer programs with small integrality gap are criticalto the success of such approximation algorithms. The immediate program is i) to develop relaxations withbounded integrality gap for the optimization problems of interest or show none exists, ii) to develop combi-natorial algorithms for solving the relaxations where possible, and iii) to develop provably good strategiesfor converting the fractional solutions to the relaxations to integral solution. There has been considerableresearch activity on the hardness of approximations in the last few years and several deep results on the hard-ness of approximations have been obtained. The focus of this research is on the design of approximationalgorithms and we will draw on the results on hardness of approximations to guide the program.On the theoretical front we will push the frontier in approximation algorithms design. Research conducted aspart of this project will have prospect for commercialization and will be of immediate interest to the industry.Knowledge generated will be protected using patents (where applicable) and disseminated in high qualityjournals and conferences. The program will produce highly skilled manpower; skilled in the use of discreteoptimization theory and tools.