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

合作研究：AF：媒介：现实生活问题的模型和算法的设计与分析

• 批准号: 1955351
• 负责人: Konstantin Makarychev
• 金额: $ 72.42万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1955351&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Design

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.

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

项目成果

Local Correlation Clustering with Asymmetric Classification Errors

• 发表时间: 2021-08
• 期刊: ArXiv
• 作者: Jafar Jafarov;Sanchit Kalhan;K. Makarychev;Yury Makarychev

Near-optimal Algorithms for Explainable k-Medians and k-Means

• 发表时间: 2021-07
• 作者: K. Makarychev;Liren Shan

Two-Sided Kirszbraun Theorem

双面科斯布劳恩定理

• DOI: 10.4230/lipics.socg.2021.13
• 发表时间: 2021
• 期刊: Leibniz international proceedings in informatics
• 作者: Backurs, Arturs;Mahabadi, Sepideh;Makarychev, Konstantin;Makarychev, Yury
• 通讯作者: Makarychev, Yury

Improved Guarantees for k-means++ and k-means++ Parallel

• 发表时间: 2020-10
• 期刊: ArXiv
• 作者: K. Makarychev;Aravind Reddy;Liren Shan

Explainable k-means: don’t be greedy, plant bigger trees!

• DOI: 10.1145/3519935.3520056
• 发表时间: 2021-11
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: K. Makarychev;Liren Shan