Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McGill University

$36,000.00

New techniques and directions in approximation algorithms

EF 2011-12

Résumé
Combinatorial Optimization deals with obtaining efficient solutions to discrete problems. Most interesting combinatorial optimization problems, theoretical as well as practical, turn out to be NP-hard, and efficient algorithms which solve them exactly are not expected. One significant direction to solve these problems has been the field of approximation algorithms which computes bounds on the worst case performance of efficient heuristics. Despite significant progress over the years, several interesting and important problems remain open in the field. A primary focus of this proposal is to research new techniques for analyzing linear programming relaxations for the combinatorial optimization problems which will lead to new algorithms. In a related direction, this proposal will seek to apply the progress made on fundamental problems to real world problems in areas ranging from Airborne Network Topology Control, Wireless Mesh Networks to Multicasting in Wireless Networks.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
386494-2010
Name nom
Singh, Mohit
Department département
Computer Science, School of
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2010
Award amount
36000
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
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
2
Nb partie
5
Application title
New techniques and directions in approximation algorithms
Keyword
NSERC
Application summary
Combinatorial Optimization deals with obtaining efficient solutions to discrete problems. Most interesting combinatorial optimization problems, theoretical as well as practical, turn out to be NP-hard, and efficient algorithms which solve them exactly are not expected. One significant direction to solve these problems has been the field of approximation algorithms which computes bounds on the worst case performance of efficient heuristics. Despite significant progress over the years, several interesting and important problems remain open in the field. A primary focus of this proposal is to research new techniques for analyzing linear programming relaxations for the combinatorial optimization problems which will lead to new algorithms. In a related direction, this proposal will seek to apply the progress made on fundamental problems to real world problems in areas ranging from Airborne Network Topology Control, Wireless Mesh Networks to Multicasting in Wireless Networks.