CAREER: Modern Algorithm Design via the Optimization Lens

计算机科学是一个快速发展的领域，导致新的计算问题。例如，今天的数据正在以巨大的速度产生，而算法对数据的访问要么由于数量庞大，要么由于所有权问题而受到限制。这迫使设计师重新审视经典算法。在机器学习中，人们使用聚类算法来学习未标记的数据。然而，噪声和异常的存在可能会扭曲这一点，并且需要良好的离群值检测算法。该项目的目标是使用和增强数学优化技术，以应对这些新的算法挑战。在此过程中，该项目将创建统一的方法来解决不同领域出现的问题。反过来，这些新的想法也将导致经典优化问题的答案。该项目的工作将与本科生和研究生课程中的相关课程的创建密切相关，这些课程专注于这些新的算法见解。该项目的教育部分还包括将计算机科学和算法思维注入K-12系统的计划。具体而言，该项目侧重于三个领域。第一个领域是关于查询访问模型，其中算法只能通过询问某些类型的问题来访问数据。 一个主要的推力是完全理解的基本问题，如子模函数优化和拟阵相交的查询复杂性。 第二个领域是开发新的近似算法技术来解决聚类中的离群检测问题。该项目还将专注于更丰富的聚类目标类，从而为整数凸优化铺平道路。第三个领域是发展的原始-对偶优化模式，设计更快的并行算法，特别是完美匹配的图形，这是一个基本的问题，在算法。通过解决这些问题，该项目将创建新的算法范例，这将有助于解决一系列现代相关问题。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

Computer Science is a rapidly growing field leading to new kinds of computational problems. For example, data is being produced at a huge rate today, and an algorithm's access to it is restricted either due to sheer volume or due to ownership concerns. This forces designers to revisit classical algorithms. In machine learning, one uses clustering algorithms to learn about unlabeled data. However, the presence of noise and anomalies can distort this, and one needs good outlier-detection algorithms. The goal of this project is to use and enhance techniques from mathematical optimization to tackle these new algorithmic challenges. In doing so, the project will create unified methodologies to attack problems arising in different areas. In turn, these news ideas will also lead to answers to classical optimization problems. Work on this project will go hand-in-hand with the creation of relevant courses in undergraduate and graduate curriculum which focus on these new algorithmic insights. The educational component of this project also includes a plan for injecting computer science and algorithmic thinking into the K-12 system. In more detail, the project focusses on three areas. The first area is about query access models where algorithms can access data only via asking certain kinds of questions. A main thrust is to completely understand the query complexity of fundamental problems such as submodular function optimization and matroid intersection. The second area is the development of new approximation-algorithm techniques to tackle outlier-detection problems in clustering. The project will also focus on richer objective classes for clustering, thereby paving the way for integer convex optimization. The third area is the development of the primal-dual optimization schema to design faster parallel algorithms, especially for perfect matchings in graphs, which is a fundamental problem in algorithms. By addressing these questions, this project will create new algorithmic paradigms that will be useful for tackling a range of modern-day relevant problems.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.