AF: SMALL: Submodular Functions and Hypergraphs: Partitioning and Connectivity

AF：SMALL：子模函数和超图：分区和连接

• 批准号: 2402667
• 负责人: Karthekeyan Chandrasekaran
• 金额: $ 60万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-06-01 至 2027-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2402667&HistoricalAwards=false
• 关键词: AF; SMALL; Submodular; Functions; Hypergraphs

Submodular functions are of fundamental importance in combinatorial optimization. Their rich structural properties coupled with algorithmic tractability have led to numerous applications in discrete optimization, computer science, economics, combinatorics, and more recently in machine learning. Hypergraphs generalize graphs and are equivalent to finite set systems. Recent years have seen several new applications of hypergraphs in social network analysis, data mining and others, as well as in mathematics. Hypergraphs and submodular functions allow one to generalize numerous problems on graphs to a more abstract setting. Algorithms for these more general problems lead to powerful and unified tools for a variety of applications. Moreover, the abstraction often leads to important structural insights and simpler proofs. The research goal of this project is to develop algorithms for a class of problems that originate in graphs and generalize to hypergraphs and submodular functions. The educational goal of the project is to train two graduate students at the intersection of algorithms and combinatorial optimization, and to disseminate several recent developments in submodular functions, hypergraphs, and related graph theoretical results through courses and publicly available lecture notes. A workshop to bring together researchers working in these areas is also planned.The technical portion of the project will focus on algorithms for partitioning and connectivity problems. For submodular functions, the project will investigate polynomial-time solvability of the partitioning problem for a fixed number of parts, which is a long-standing open problem. As special cases of submodular functions, the project will focus on matroid, matrix, and hypergraph partitioning problems. For hypergraphs, the project will focus on faster algorithms and structural properties related to cuts and connectivity. These include (i) algorithms to find sparse representation of hypergraphs such as cut sparsifiers, cactus representations and Gomory-Hu trees, (ii) algorithms for representing element connectivity in graphs via hypergraphs, and (iii) parallel algorithms for hypergraph mincut and related 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.

子模函数在组合优化中至关重要。它们丰富的结构特性与算法的易处理性相结合，在离散优化、计算机科学、经济学、组合学以及最近的机器学习领域得到了广泛的应用。超图概括了图，相当于有限集系统。近年来，超图在社交网络分析、数据挖掘等以及数学中出现了一些新的应用。超图和子模函数允许人们将图上的许多问题概括为更抽象的设置。针对这些更普遍的问题的算法为各种应用程序带来了强大且统一的工具。此外，抽象通常会带来重要的结构见解和更简单的证明。该项目的研究目标是为源自图并推广到超图和子模函数的一类问题开发算法。该项目的教育目标是在算法和组合优化的交叉领域培养两名研究生，并通过课程和公开讲稿传播子模函数、超图和相关图理论结果的最新进展。还计划举办一个研讨会，将这些领域的研究人员聚集在一起。该项目的技术部分将重点关注分区和连接问题的算法。对于子模函数，该项目将研究固定数量部分的划分问题的多项式时间可解性，这是一个长期存在的开放问题。作为子模函数的特例，该项目将重点关注拟阵、矩阵和超图划分问题。对于超图，该项目将专注于与切割和连接相关的更快的算法和结构属性。其中包括（i）用于查找超图稀疏表示的算法，例如切割稀疏器、仙人掌表示和 Gomory-Hu 树，（ii）用于通过超图表示图中元素连接性的算法，以及（iii）用于超图最小割和相关问题的并行算法该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。