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

子模函数在组合优化中具有重要意义。它们丰富的结构特性和算法的易操作性使其在离散优化、计算机科学、经济学、组合学以及最近的机器学习中得到了广泛的应用。超图是图的泛化，等价于有限集系统。近年来，超图在社会网络分析、数据挖掘和其他领域以及数学中都有了一些新的应用。超图和子模函数允许人们将图上的许多问题推广到更抽象的环境中。针对这些更一般问题的算法为各种应用程序提供了强大而统一的工具。此外，抽象往往导致重要的结构洞察力和更简单的证明。这个项目的研究目标是为一类起源于图并推广到超图和子模函数的问题开发算法。该项目的教育目标是在算法和组合优化的交叉点上培养两名研究生，并通过课程和公开可用的课堂讲稿传播子模函数、超图和相关图论结果的几个最新发展。还计划举办一次研讨会，将这些领域的研究人员聚集在一起。该项目的技术部分将侧重于分区和连接问题的算法。对于子模函数，该项目将研究固定数量的部分的划分问题的多项式时间可解性，这是一个长期开放的问题。作为子模函数的特例，该项目将专注于拟阵、矩阵和超图划分问题。对于超图，该项目将专注于与切割和连通性相关的更快的算法和结构属性。这些奖项包括(I)寻找超图的稀疏表示的算法，如割稀疏器、仙人掌表示和Gomory-Hu树，(Ii)通过超图表示图中元素连通性的算法，以及(Iii)超图最小割和相关问题的并行算法。该奖项反映了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.