Collaborative Research: AF: Medium: Design and Analysis of Models and Algorithms for Real-life Problems

近年来，计算机和数据科学在商业、工程、医疗保健和科学领域的应用急剧增加。人们使用计算机分析越来越多的数据，解决越来越难的问题。处理越来越多的数据和解决越来越难的问题需要新的高性能算法。该项目将探索算法设计中有前景的新方向，旨在开发适合于处理现实数据的高效算法。为此，研究人员将研究现实问题的结构，分析数据中的隐藏模式，并为现实问题创建新的数学和统计模型。他们将利用他们的发现来改进现有的算法，并开发新的、高效的算法。研究人员将确保新的算法是“软件开发人员友好的”：这些算法将是快速和容易实现的，并将依赖于现有的技术。该项目将专注于机器学习、运筹学和离散优化中出现的计算问题。它将通过识别将它们与最坏情况（在实践中很少或从未出现）区分开来的属性，并为它们设计更好的算法（具有可证明的性能保证），从而提高对现实生活中问题实例本质的理解。它将为基本理论问题提供（部分）答案：为什么许多启发式计算难题在实践中工作得很好？如何为现实生活中的问题实例设计和正式分析算法？为了回答这些问题，研究团队将为现实数据创建新的模型，开发新的算法，并引入新的数学技术来分析这些算法。研究结果将与机器学习、优化和其他领域的研究人员和实践者相关；特别是，这些结果将为他们提供新的实用算法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Recent years have seen a dramatic rise in applications of computer and data science in business, engineering, healthcare, and science. People use computers for analyzing increasingly large amounts of data and solving progressively more difficult problems. Processing growing amounts of data and solving increasingly hard problems require new high-performance algorithms. This project will explore new promising directions in algorithm design with the aim of developing efficient algorithms that are tailored to working with real-life data. To this end, the investigators will study the structure of real-life problems, analyze hidden patterns in the data, and create new mathematical and statistical models of real-world problems. They will use their findings to improve existing algorithms and develop new, highly efficient ones. The investigators will ensure that the new algorithms are "software developer-friendly": these algorithms will be fast and easy to implement, and will rely on existing technologies.The project will focus on computational problems that arise in machine learning, operations research, and discrete optimization. It will advance understanding of the nature of real-life problem instances, by identifying properties that distinguish them from worst-case instances (which rarely or never appear in practice) and designing better algorithms (with provable performance guarantees) for them. It will provide a (partial) answer to fundamental theoretical questions: Why do many heuristics for computationally hard problems work well in practice? And how can one design and formally analyze algorithms for real-life problem instances? To answer these questions, the team of investigators will create new models for real-life data, develop new algorithms, and introduce new mathematical techniques for analyzing these algorithms. The results will be relevant to researchers and practitioners in machine learning, optimization, and other areas; in particular, the results will provide them with new practical algorithms.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.