Efficient algorithms for optimization problems and their interplay with polyhedral combinatorics

点击翻译按钮获取中文摘要

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.