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

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