Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$36,000.00

Approximation Algorithms for Network Design

FY 2024-25

Summary
Complex networks play an increasingly larger role in the world around us. For example, billions of people around the world rely every single day on the internet, on social networks, and on transportation systems. Many of these systems are designed, constructed, and analyzed by using tools and methods from the disciplines of Operations Research, Combinatorial Optimization, and Theoretical Computer Science. In these disciplines, the key paradigm is to construct an abstract model of the real-world system, called a network model, and then to design algorithms to find the best networks that satisfy the requirements of the real-world system. For example, the greedy algorithm can compute a cheapest network that connects all the nodes of a network, a so-called minimum spanning tree. Similar ``network problems'' arise in many practical contexts such as the design of fault-tolerant communication networks, congestion control for road traffic, and the analysis of social networks. Unfortunately, many of the network problems arising in practical contexts are NP-hard. This means that optimal solutions cannot be computed in a reasonable running time, modulo a widely accepted hypothesis called the P .not.= NP conjecture. Consequently, researchers have changed their goals to designing and analyzing approximation algorithms, that is, efficient algorithms that find solutions that are within a guaranteed factor of the optimal solution. My research focuses on approximation algorithms for important problems in network design. In the last few years, I have trained and mentored several HQP, and we have published our algorithmic results in the leading conferences and journals. Since my research focus is on theory and algorithms, my HQP training develops skills such as modeling, problem solving, analysis, presentation, and writing. My graduated HQP (over the last 6 years) are now either working in the Education/Software/Tech sectors in North America, or they are Postdocs or Ph.D. students in top-tier universities. I plan to continue with my HQP training program, with special focus on EDI (Equity, Diversity and Inclusivity), building on my substantial contributions to EDI in my HQP training over the last 6 years. The long-term impact of my research program is theoretical, and it enhances Canada's position as a leader in the disciplines of Combinatorial Optimization and Theoretical Computer Science.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2024-04473
Name nom
Cheriyan, Joseph
Department département
Combinatorics and Optimization - 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
2024
Competition year année de concours
2024
Award amount
36000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Approximation Algorithms for Network Design
Keywords
approximation algorithms; combinatorial optimization; hardness of approximation; parametrized algorithms; linear programming relaxations; primal-dual method; capacitated network design; flexible network design; network flows; traveling salesman problem (tsp)
Application summary
Complex networks play an increasingly larger role in the world around us. For example, billions of people around the world rely every single day on the internet, on social networks, and on transportation systems. Many of these systems are designed, constructed, and analyzed by using tools and methods from the disciplines of Operations Research, Combinatorial Optimization, and Theoretical Computer Science. In these disciplines, the key paradigm is to construct an abstract model of the real-world system, called a network model, and then to design algorithms to find the best networks that satisfy the requirements of the real-world system. For example, the greedy algorithm can compute a cheapest network that connects all the nodes of a network, a so-called minimum spanning tree. Similar ``network problems'' arise in many practical contexts such as the design of fault-tolerant communication networks, congestion control for road traffic, and the analysis of social networks. Unfortunately, many of the network problems arising in practical contexts are NP-hard. This means that optimal solutions cannot be computed in a reasonable running time, modulo a widely accepted hypothesis called the P .not.= NP conjecture. Consequently, researchers have changed their goals to designing and analyzing approximation algorithms, that is, efficient algorithms that find solutions that are within a guaranteed factor of the optimal solution. My research focuses on approximation algorithms for important problems in network design. In the last few years, I have trained and mentored several HQP, and we have published our algorithmic results in the leading conferences and journals. Since my research focus is on theory and algorithms, my HQP training develops skills such as modeling, problem solving, analysis, presentation, and writing. My graduated HQP (over the last 6 years) are now either working in the Education/Software/Tech sectors in North America, or they are Postdocs or Ph.D. students in top-tier universities. I plan to continue with my HQP training program, with special focus on EDI (Equity, Diversity and Inclusivity), building on my substantial contributions to EDI in my HQP training over the last 6 years. The long-term impact of my research program is theoretical, and it enhances Canada's position as a leader in the disciplines of Combinatorial Optimization and Theoretical Computer Science.