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

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

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.