Grant: Discovery Grants Program - Individual
University of Waterloo
$46,000.00
Approximation algorithms for NP-hard problems
EF 2018-19
Résumé
Network design, network flows, and graph connectivity occur as core topics in Theoretical Computer Science, Operations Research, and Combinatorial Optimization. Many important algorithmic 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 and congestion control for urban road traffic. 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.*My current and planned research focuses on the following three broad interlocking themes. I discuss two of these topics below, and my proposal discusses all the topics in full.*1. Design of approximately minimum-cost networks, including the Traveling Salesman Problem (TSP) and its variants.*2. Design of networks subject to node-connectivity requirements.*3. Lift-and-Project methods for the Asymmetric TSP and related problems.*The most famous problem in all of discrete optimization is the TSP. The best known algorithmic result is the 3/2-approximation algorithm due to Christofides from 1976. It has long been conjectured that there exists a 4/3-approximation algorithm for the TSP, and that there exists a 3/2-approximation algorithm for a variant called the s-t path TSP.*Two of the outstanding open questions on this topic that I am researching are the following:*(*) Improve on the approximation guarantee of 7/5 for an important special case called the GRAPHIC TSP, possibly based on a combination of LP-rounding techniques and ear-decomposition techniques.*(*) Improve on the approximation guarantee of 8/5 for the s-t path TSP, possibly based on LP-rounding techniques, coupled with improved structural results on the support graph of LP solutions.*The second broad theme of my research addresses the design of networks subject to node-connectivity requirements. One of the basic problems in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some pre-specified connectivity requirements. The area of minimum-cost network design subject to EDGE-connectivity requirements flourished in the 1990s, and there were a number of landmark results. Progress has been much slower on similar problems with NODE-connectivity requirements, despite more than a decade of active research. Very recently, in a paper co-authored with L.Vegh (Proc. IEEE FOCS 2013), I have obtained a major advance on a fundamental problem in this area: we have a 6-approximation algorithm for the minimum-cost k-node connected spanning subgraph problem, assuming that the number of nodes is at least k^4. Our results and techniques have opened up many new directions in the design of networks subject to node-connectivity requirements. I plan to continue research on these topics, together with graduate students and postdocs.*In summary, the high-level goal of my research agenda is to provide significant advances in the areas of Network Design and related areas of Combinatorial Optimization. This has the potential to improve the results and techniques available to all researchers who work in this core area of the computational sciences. Problems such as the TSP are ubiquitous in all modern societies, including Canada; the economy and infrastructure are based on logistics, transport, networks, and on the optimal allocation of scarce resources to critical tasks.
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
RGPIN-2014-04351
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
2018
Competition year année de concours
2014
Award amount
46000
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
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
5
Nb partie
5
Application title
Approximation algorithms for NP-hard problems
Keyword
NSERC
Application summary
Network design, network flows, and graph connectivity occur as core topics in Theoretical Computer Science, Operations Research, and Combinatorial Optimization. Many important algorithmic 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 and congestion control for urban road traffic. 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.*My current and planned research focuses on the following three broad interlocking themes. I discuss two of these topics below, and my proposal discusses all the topics in full.*1. Design of approximately minimum-cost networks, including the Traveling Salesman Problem (TSP) and its variants.*2. Design of networks subject to node-connectivity requirements.*3. Lift-and-Project methods for the Asymmetric TSP and related problems.*The most famous problem in all of discrete optimization is the TSP. The best known algorithmic result is the 3/2-approximation algorithm due to Christofides from 1976. It has long been conjectured that there exists a 4/3-approximation algorithm for the TSP, and that there exists a 3/2-approximation algorithm for a variant called the s-t path TSP.*Two of the outstanding open questions on this topic that I am researching are the following:*(*) Improve on the approximation guarantee of 7/5 for an important special case called the GRAPHIC TSP, possibly based on a combination of LP-rounding techniques and ear-decomposition techniques.*(*) Improve on the approximation guarantee of 8/5 for the s-t path TSP, possibly based on LP-rounding techniques, coupled with improved structural results on the support graph of LP solutions.*The second broad theme of my research addresses the design of networks subject to node-connectivity requirements. One of the basic problems in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some pre-specified connectivity requirements. The area of minimum-cost network design subject to EDGE-connectivity requirements flourished in the 1990s, and there were a number of landmark results. Progress has been much slower on similar problems with NODE-connectivity requirements, despite more than a decade of active research. Very recently, in a paper co-authored with L.Vegh (Proc. IEEE FOCS 2013), I have obtained a major advance on a fundamental problem in this area: we have a 6-approximation algorithm for the minimum-cost k-node connected spanning subgraph problem, assuming that the number of nodes is at least k^4. Our results and techniques have opened up many new directions in the design of networks subject to node-connectivity requirements. I plan to continue research on these topics, together with graduate students and postdocs.*In summary, the high-level goal of my research agenda is to provide significant advances in the areas of Network Design and related areas of Combinatorial Optimization. This has the potential to improve the results and techniques available to all researchers who work in this core area of the computational sciences. Problems such as the TSP are ubiquitous in all modern societies, including Canada; the economy and infrastructure are based on logistics, transport, networks, and on the optimal allocation of scarce resources to critical tasks.