Grant: Discovery Grants Program - Individual
University of Waterloo
$30,000.00
Approximation algorithms for NP-hard problems in network design
EF 2011-12
Résumé
My current and planned research focuses on outstanding open questions in the area of
approximation algorithms for problems in network design, graph connectivity, and network
flows. These topics occupy a central position in Theoretical Computer Science and Combinatorial Optimization. Moreover, they arise in many practical contexts such as the design of fault-tolerant communication networks. Many of these problems are NP-hard. This means that optimal solutions cannot be computed in a reasonable running time, modulo the conjecture that P is not equal to NP. Hence, research has focused on approximation algorithms, that is, algorithms that run efficiently (in polynomial time) and find solutions that are within a guaranteed factor of the optimal solution.
I have attacked some of the outstanding open topics in the area (jointly with co-authors),
and we have achieved substantial advances. The problem of designing networks that
satisfy vertex connectivity requirements is a hot topic. Together with Vetta, I have
given constant-factor approximation algorithms for some key special cases of practical importance, for example, metric-cost subset k-connectivity. Another topic of high interest pertains to packing Steiner trees in a given graph. Together with Salavatipour, I have obtained both approximation algorithms and hardness results that serve to classify the tractability of the different problems (models); these results have implications for network coding, which is an exciting emerging area of practical and theoretical significance.
My current and future research focuses on these topics, and the high-level goal is to achieve algorithmic advances and to obtain a better understanding of the fundamental issues.
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
138432-2009
Name nom
Cheriyan, Joseph
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2009
Award amount
30000
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
804
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
Communication systems and services (planning, organization, services)
Area of application fr
Systèmes et services de communications (planification, organisation et services)
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 problems in network design
Keyword
NSERC
Application summary
My current and planned research focuses on outstanding open questions in the area of
approximation algorithms for problems in network design, graph connectivity, and network
flows. These topics occupy a central position in Theoretical Computer Science and Combinatorial Optimization. Moreover, they arise in many practical contexts such as the design of fault-tolerant communication networks. Many of these problems are NP-hard. This means that optimal solutions cannot be computed in a reasonable running time, modulo the conjecture that P is not equal to NP. Hence, research has focused on approximation algorithms, that is, algorithms that run efficiently (in polynomial time) and find solutions that are within a guaranteed factor of the optimal solution.
I have attacked some of the outstanding open topics in the area (jointly with co-authors),
and we have achieved substantial advances. The problem of designing networks that
satisfy vertex connectivity requirements is a hot topic. Together with Vetta, I have
given constant-factor approximation algorithms for some key special cases of practical importance, for example, metric-cost subset k-connectivity. Another topic of high interest pertains to packing Steiner trees in a given graph. Together with Salavatipour, I have obtained both approximation algorithms and hardness results that serve to classify the tractability of the different problems (models); these results have implications for network coding, which is an exciting emerging area of practical and theoretical significance.
My current and future research focuses on these topics, and the high-level goal is to achieve algorithmic advances and to obtain a better understanding of the fundamental issues.