CAREER: Modern Algorithm Design via the Optimization Lens

职业：通过优化镜头进行现代算法设计

• 批准号: 2041920
• 负责人: Deeparnab Chakrabarty
• 金额: $ 54.18万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-04-01 至 2026-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2041920&HistoricalAwards=false
• 关键词: CAREER; Modern; Algorithm; Design; via

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.

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

项目成果

A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids

$d$ 维超网格上布尔函数的 $d^{1/2 o(1)}$ 单调性测试器

• 发表时间: 2023
• 期刊: Annual Symposium on Foundations of Computer Science
• 作者: Hadley Black, Deeparnab Chakrabarty

Improved Lower Bounds for Submodular Function Minimization

子模函数最小化的改进下界

• DOI: 10.1109/focs54457.2022.00030
• 发表时间: 2022
• 期刊: Symposium on Foundations of Computer Science (FOCS 2022
• 作者: Chakrabarty, Deeparnab;Graur, Andrei;Jiang, Haotian;Sidford, Aaron
• 通讯作者: Sidford, Aaron

Approximation Algorithms for Continuous Clustering and Facility Location Problems

连续聚类和设施选址问题的近似算法

• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Chakrabarty, Deeparnab;Negahbani, Maryam;Sarkar, Ankita
• 通讯作者: Sarkar, Ankita

Revisiting Priority k-Center: Fairness and Outliers

• DOI: 10.4230/lipics.icalp.2021.21
• 发表时间: 2021-03
• 期刊: ArXiv
• 作者: Tanvi Bajpai;Deeparnab Chakrabarty;C. Chekuri;Maryam Negahbani

Parallel Submodular Function Minimization

并行子模函数最小化

• 发表时间: 2023
• 期刊: Advances in neural information processing systems
• 作者: Chakrabarty, Deeparnab;Graur, Andrei;Jiang, Haotian;Sidford, Aaron
• 通讯作者: Sidford, Aaron