Efficient algorithms for optimization problems and their interplay with polyhedral combinatorics

优化问题的有效算法及其与多面体组合的相互作用

• 批准号: RGPIN-2019-04413
• 负责人: Sanità, Laura
• 金额: $ 3.5万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=689674
• 关键词: Efficient; algorithms; optimization; problems; their

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

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