Grant: Discovery Grants Program - Individual
University of Lethbridge
$20,000.00
Approximation Algorithms for NP-hard Optimization Problems
EF 2016-17
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 the
quality of solution for the computation time. Approximation algorithms do precisely that. Approximation
algorithms not only provide an approximate solution in polynomial time, they also provide a certificate of
optimality for the solution. One can always refine and tune an approximation algorithm to specific class of
instances 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. We
will design approximation algorithms for problems arising in the bioinformatics, facility location, schedul-
ing, and machine learning domains. Our approach for designing approximation algorithms has theoretical
underpinnings in combinatorial algorithms, linear and semi-definite programming. Linear programming
based 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 integral
solution using some scheme. Care is taken to ensure that the process of converting the fractional solution to
an 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 using
the primal-dual schema. Primal-dual schema has the advantage that one can work with an exponential sized
formulation without having to resort to a separation oracle. Approaches based on the primal-dual schema
have 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 better
than the integrality gap of the relaxation. Therefore integer programs with small integrality gap are critical
to the success of such approximation algorithms. The immediate program is i) to develop relaxations with
bounded 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 strategies
for converting the fractional solutions to the relaxations to integral solution. There has been considerable
research 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 approximation
algorithms 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 as
part 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 quality
journals and conferences. The program will produce highly skilled manpower; skilled in the use of discrete
optimization theory and tools.
Programme
Discovery Grants Program - Individual
Bénéficiaire
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
2016
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
3
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 the
quality of solution for the computation time. Approximation algorithms do precisely that. Approximation
algorithms not only provide an approximate solution in polynomial time, they also provide a certificate of
optimality for the solution. One can always refine and tune an approximation algorithm to specific class of
instances 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. We
will design approximation algorithms for problems arising in the bioinformatics, facility location, schedul-
ing, and machine learning domains. Our approach for designing approximation algorithms has theoretical
underpinnings in combinatorial algorithms, linear and semi-definite programming. Linear programming
based 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 integral
solution using some scheme. Care is taken to ensure that the process of converting the fractional solution to
an 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 using
the primal-dual schema. Primal-dual schema has the advantage that one can work with an exponential sized
formulation without having to resort to a separation oracle. Approaches based on the primal-dual schema
have 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 better
than the integrality gap of the relaxation. Therefore integer programs with small integrality gap are critical
to the success of such approximation algorithms. The immediate program is i) to develop relaxations with
bounded 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 strategies
for converting the fractional solutions to the relaxations to integral solution. There has been considerable
research 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 approximation
algorithms 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 as
part 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 quality
journals and conferences. The program will produce highly skilled manpower; skilled in the use of discrete
optimization theory and tools.