Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$48,000.00

Efficient algorithms for optimization problems and their interplay with polyhedral combinatorics

EF 2020-21

Résumé
Complex optimization problems are frequent and crucial in everyday life. As an example, modern life heavily demands fast data transmission on networks, time-effective scheduling of trains and airplanes, or facilities such as fire stations or hospitals, being built in strategic locations. Unfortunately, most optimization problems are computationally intractable (NP-hard) and unlikely to admit efficient algorithms that find an optimal solution. One way to address this intractability is to focus on so-called approximation algorithms. Specifically, an -approximation algorithm is an efficient algorithm that always delivers a solution of value within a factor of the optimum. The investigation of approximation algorithms started more than 50 years ago, and their popularity consistently increased with time. In fact, many impressive results have been proved in recent years if we inspect the “best paper awards” given by the most prestigious conferences in theoretical computer science (such as STOC, FOCS, and SODA) in the last 10 years, we can see that roughly one third of such awards went to papers related to approximation algorithms. As such, it is not surprising that nowadays this research area is tremendously active, and it is my primary area of expertise. A long-term goal of this proposal is developing new approximation algorithms for fundamental optimization problems, targeting the areas of network optimization and algorithmic game theory. In the development of the above algorithms, a crucial role is played by techniques coming from the area of polyhedral combinatorics. In fact, polyhedral results are often at the heart of (exact and approximation) algorithms for solving optimization problems. For this reason, another long-term goal of the proposal is studying fundamental properties and structures of polyhedra. A famous polyhedral concept is that of diameter, defined as the maximum value of the distance between a pair of vertices of a polyhedron. Despite decades of studies, it is still not known whether the diameter of a d-dimensional polytope with n facets can be bounded by a polynomial function of n and d. This is a fundamental open question in discrete mathematics, that is also somewhat related to a major open problem in the field: namely, finding a strongly-polynomial time algorithm for Linear Programming. This proposal aims at developing new results on computing the diameter, with a special emphasis on polyhedra that correspond to the set of feasible solutions of classical combinatorial optimization problems. Although most of the proposed research questions are of a theoretical nature, they are motivated by real-world optimization problems. Furthermore, polyhedral techniques are nowadays a fundamental tool employed to design solvers for large-scale industrial optimization problems. Therefore, I expect that this proposal will produce results and methods with high potential for applications in the industry, for the benefit of Canada.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2019-04413
Name nom
Sanità, Laura
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
2020
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 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
Installment
inst:2-5
Partie
4
Nb partie
5
Application title
Efficient algorithms for optimization problems and their interplay with polyhedral combinatorics
Keyword
NSERC
Application summary
Complex optimization problems are frequent and crucial in everyday life. As an example, modern life heavily demands fast data transmission on networks, time-effective scheduling of trains and airplanes, or facilities such as fire stations or hospitals, being built in strategic locations. Unfortunately, most optimization problems are computationally intractable (NP-hard) and unlikely to admit efficient algorithms that find an optimal solution. One way to address this intractability is to focus on so-called approximation algorithms. Specifically, an -approximation algorithm is an efficient algorithm that always delivers a solution of value within a factor of the optimum. The investigation of approximation algorithms started more than 50 years ago, and their popularity consistently increased with time. In fact, many impressive results have been proved in recent years if we inspect the “best paper awards” given by the most prestigious conferences in theoretical computer science (such as STOC, FOCS, and SODA) in the last 10 years, we can see that roughly one third of such awards went to papers related to approximation algorithms. As such, it is not surprising that nowadays this research area is tremendously active, and it is my primary area of expertise. A long-term goal of this proposal is developing new approximation algorithms for fundamental optimization problems, targeting the areas of network optimization and algorithmic game theory. In the development of the above algorithms, a crucial role is played by techniques coming from the area of polyhedral combinatorics. In fact, polyhedral results are often at the heart of (exact and approximation) algorithms for solving optimization problems. For this reason, another long-term goal of the proposal is studying fundamental properties and structures of polyhedra. A famous polyhedral concept is that of diameter, defined as the maximum value of the distance between a pair of vertices of a polyhedron. Despite decades of studies, it is still not known whether the diameter of a d-dimensional polytope with n facets can be bounded by a polynomial function of n and d. This is a fundamental open question in discrete mathematics, that is also somewhat related to a major open problem in the field: namely, finding a strongly-polynomial time algorithm for Linear Programming. This proposal aims at developing new results on computing the diameter, with a special emphasis on polyhedra that correspond to the set of feasible solutions of classical combinatorial optimization problems. Although most of the proposed research questions are of a theoretical nature, they are motivated by real-world optimization problems. Furthermore, polyhedral techniques are nowadays a fundamental tool employed to design solvers for large-scale industrial optimization problems. Therefore, I expect that this proposal will produce results and methods with high potential for applications in the industry, for the benefit of Canada.