Efficient algorithms for optimization problems and their interplay with polyhedral combinatorics

复杂的优化问题在日常生活中经常出现，而且至关重要。例如，现代生活强烈要求在网络上快速传输数据，及时调度火车和飞机，或者在战略位置建造消防站或医院等设施。不幸的是，大多数优化问题在计算上是难以处理的（NP-hard），不太可能允许找到最优解的有效算法。解决这一棘手问题的一种方法是关注所谓的近似算法。具体来说，-近似算法是一种有效的算法，它总是在最优因子的范围内提供值的解。对近似算法的研究始于50多年前，随着时间的推移，它们的普及程度不断提高。事实上，近年来已经证明了许多令人印象深刻的结果，如果我们检查过去10年理论计算机科学中最负盛名的会议（如STOC， FOCS和SODA）颁发的“最佳论文奖”，我们可以看到，大约三分之一的此类奖项授予了与近似算法相关的论文。因此，毫不奇怪，现在这个研究领域非常活跃，这是我的主要专业领域。***本提案的长期目标是为基本优化问题开发新的近似算法，针对网络优化和算法博弈论领域。******在上述算法的发展中，来自多面体组合学领域的技术起着至关重要的作用。事实上，多面体结果通常是解决优化问题的（精确和近似）算法的核心。因此，该提案的另一个长期目标是研究多面体的基本性质和结构。***一个著名的多面体概念是直径，定义为多面体一对顶点之间距离的最大值。尽管经过了几十年的研究，我们仍然不知道n个面的d维多面体的直径是否可以由n和d的多项式函数限定。这是离散数学中的一个基本开放问题，也与该领域的一个主要开放问题有关：即寻找线性规划的强多项式时间算法。***本提案旨在发展计算直径的新结果，特别强调多面体对应于经典组合优化问题的可行解集。******虽然大多数提出的研究问题都是理论性的，但它们是由现实世界的优化问题驱动的。此外，多面体技术是当今用于设计大规模工业优化问题求解器的基本工具。因此，我希望这一提案将产生具有很高应用潜力的结果和方法，以造福加拿大。**

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. **