AF: Small: Algorithms for Solving Real-Life Instances of Optimization and Clustering Problems

该项目旨在为商业，工程和科学中出现的计算问题开发有效的算法。该项目将对理论计算机科学（TCS）产生影响，提高我们对现实生活中实例的性质的理解，并为它们设计更好的算法-具有可证明的性能保证。此外，研究结果将与计算机科学其他领域的研究人员相关，包括机器学习和优化。特别是，该项目将为研究人员提供新的实用算法。通过其广泛的成果，该项目将加强TCS与计算机科学其他领域之间的联系。此外，该项目将引起数学、数学物理和统计学领域研究人员的兴趣，部分原因是本提案中考虑的一个关键模型已经在这些领域进行了介绍和研究。PI将与芝加哥丰田技术研究所（TTIC）和芝加哥大学的研究生和本科生合作开展该项目。此外，他还将邀请其他大学的博士生在夏季参与该项目。PI将在其研究生课程中纳入本提案的主题。具体来说，他将在他的研究生算法课程中包括关于这个主题的介绍材料，并在他的计算机科学中的度量几何课程中包括更高级的材料。在商业、工程和科学中出现的许多问题在最坏的情况下是非常困难的：对他们来说，没有“通用的”有效算法--iidoEe，在合理的（多项式）时间内解决所有可能实例的算法。然而，现实生活中的实例通常比最困难的实例简单得多。该项目的目标是确定是什么使现实生活中的实例计算上易于处理，并设计有效的算法来解决这些问题。这些算法将解决许多现实生活中的计算问题的实例，利用他们的结构属性（在同一时间，算法可能无法解决最困难的情况下，然而，几乎从来没有出现在实践中）。为了设计有效的算法-与可证明的性能保证-为现实生活中的计算问题的实例，一个必须定义一个形式化的模型为现实生活中的实例。该提案将探索现有的生成和描述模型，用于聚类和优化问题的实际实例，包括半随机随机块模型和基于不同稳定性假设的模型。该项目还将开发新的、更先进的模型。PI将为这些模型设计新的算法，并分析现有的算法。

The project aims to develop efficient algorithms for computational problems that arise in business, engineering, and science. The project will have an impact on theoretical computer science (TCS) by improving our understanding of the nature of real-life instances and designing better algorithms -- with provable performance guarantees -- for them. Additionally, the results will be relevant to researchers in other areas of computer science, including machine learning and optimization. In particular, this project will provide researchers with new practical algorithms. Through its wide-reaching results, the project will strengthen the connection between TCS and other areas of computer science. Further, the project will be of interest to researchers in mathematics, mathematical physics, and statistics, in part because one of the key models considered in this proposal has been introduced and studied in these fields.The PI will collaborate on this project with graduate and undergraduate students at the Toyota Technological Institute at Chicago (TTIC) and the University of Chicago. Additionally, he will invite PhD students from other universities to work on the project during summer months. The PI will incorporate the topic of this proposal in his graduate courses. Specifically, he will include introductory material on the topic in his graduate Algorithms course and more advanced material in his course on metric geometry in computer science.Many problems that arise in business, engineering, and science are very hard in the worst case: for them, there are no "universal" efficient algorithms -- i.e., algorithms that solve all possible instances in reasonable (polynomial) time. However, real-life instances are usually considerably simpler than the most difficult ones. The goal of this project is to identify what makes real-life instances computationally tractable and to design efficient algorithms for solving them. These algorithms will solve many real-life instances of computational problems by exploiting their structural properties (at the same time, the algorithms may fail to solve the most difficult instances, which, however, almost never appear in practice).In order to design efficient algorithms -- with provable performance guarantees -- for real-life instances of computational problems, one has to define a formal model for real-life instances. This proposal will explore existing generative and descriptive models for real-life instances of clustering and optimization problems, including semi-random stochastic block models and models based on different stability assumptions. The project will also develop new, more advanced models. The PI will design new algorithms for these models and analyze existing heuristics.