Grant: Discovery Grants Program - Individual
University of Waterloo
$48,000.00
Approximation Algorithms for NP-Hard Problems
FY 2019-20
Summary
Network design, network flows, and graph connectivity are core topics in Theoretical Computer Science, Operations Research, and Combinatorial Optimization. Important algorithmic and structural paradigms were developed in the context of these topics, such as the greedy algorithm for minimum spanning trees and the max-flow min-cut theorem for network flows. Moreover, these topics 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. Many of the problems arising in practical contexts are NP-hard. This means that optimal solutions cannot be computed in a reasonable running time, modulo the P .not.= NP conjecture. Hence, research has focused on approximation algorithms, i.e., efficient algorithms that find solutions that are within a guaranteed factor of the optimal solution.******In the design and analysis of approximation algorithms, I am using methods such as: algorithms and theory from combinatorial optimization (in particular, matchings and network flows), rounding of linear-programming relaxations, the primal-dual method, lift-and-project methods, and dynamic programming.******I plan to attack some outstanding open questions in network design jointly with my graduate students and co-authors, building on my recent major advances and journal publications.******Three key modules of my research program are summarized below.******(A) Network Design for Node-Connectivity Requirements******A basic problem in network design, called the NC-SNDP, is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified NODE-connectivity requirements. I am attacking (with my grad students) a fundamental open problem: design an approximation algorithm for NC-SNDP whose guarantee is independent of the number of nodes/edges/terminals of the network G.******(B) Thin trees and the Traveling Salesman Problem (TSP)******The thinness parameter of a spanning tree T is the maximum over all cuts of the proportion of the edges of T in the cut. Goddyn conjectured that for any required thinness, a graph of sufficiently large edge-connectivity has a spanning tree with that thinness. An algorithmic (poly-time) proof would give major advances on approximation algorithms for ATSP. My long-term goal is such a proof. I am designing (with my grad students) efficient algorithms for finding thin spanning trees in special classes of graphs.******(C) Lift-and-Project Systems for Combinatorial Optimization******A key open question in the area is to improve on the approximation guarantee of two for the minimum-cost 2-edge connected spanning subgraph (2-ECSS) problem. My immediate goal is to derive an approximation guarantee better than two for a special case of this problem called the Forest Augmentation Problem (FAP) relative to a relaxation of FAP obtained via Lift-and-Project methods. This will generalize results that I have published with Gao (my completed Ph.D. student).**
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-04197
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
2019
Competition year année de concours
2019
Award amount
48000
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
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
Installment
inst:1 - 5
Partie
1
Nb partie
5
Application title
Approximation Algorithms for NP-Hard Problems
Keyword
NSERC
Application summary
Network design, network flows, and graph connectivity are core topics in Theoretical Computer Science, Operations Research, and Combinatorial Optimization. Important algorithmic and structural paradigms were developed in the context of these topics, such as the greedy algorithm for minimum spanning trees and the max-flow min-cut theorem for network flows. Moreover, these topics 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. Many of the problems arising in practical contexts are NP-hard. This means that optimal solutions cannot be computed in a reasonable running time, modulo the P .not.= NP conjecture. Hence, research has focused on approximation algorithms, i.e., efficient algorithms that find solutions that are within a guaranteed factor of the optimal solution.******In the design and analysis of approximation algorithms, I am using methods such as: algorithms and theory from combinatorial optimization (in particular, matchings and network flows), rounding of linear-programming relaxations, the primal-dual method, lift-and-project methods, and dynamic programming.******I plan to attack some outstanding open questions in network design jointly with my graduate students and co-authors, building on my recent major advances and journal publications.******Three key modules of my research program are summarized below.******(A) Network Design for Node-Connectivity Requirements******A basic problem in network design, called the NC-SNDP, is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified NODE-connectivity requirements. I am attacking (with my grad students) a fundamental open problem: design an approximation algorithm for NC-SNDP whose guarantee is independent of the number of nodes/edges/terminals of the network G.******(B) Thin trees and the Traveling Salesman Problem (TSP)******The thinness parameter of a spanning tree T is the maximum over all cuts of the proportion of the edges of T in the cut. Goddyn conjectured that for any required thinness, a graph of sufficiently large edge-connectivity has a spanning tree with that thinness. An algorithmic (poly-time) proof would give major advances on approximation algorithms for ATSP. My long-term goal is such a proof. I am designing (with my grad students) efficient algorithms for finding thin spanning trees in special classes of graphs.******(C) Lift-and-Project Systems for Combinatorial Optimization******A key open question in the area is to improve on the approximation guarantee of two for the minimum-cost 2-edge connected spanning subgraph (2-ECSS) problem. My immediate goal is to derive an approximation guarantee better than two for a special case of this problem called the Forest Augmentation Problem (FAP) relative to a relaxation of FAP obtained via Lift-and-Project methods. This will generalize results that I have published with Gao (my completed Ph.D. student).**