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

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

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.