In submodular k-partition, the input is a non-negative submodular function f defined over a finite ground set V (given by an evaluation oracle) along with a positive integer k and the goal is to partition the ground set V into k non-empty parts V_1, V_2, ..., V_k in order to minimize sum_{i=1}^k f(V_i). Submodular k-partition generalizes partitioning problems over several interesting structures including graphs, hypergraphs, and matrices. Submodular k-partition is NP-hard and is O(k)-approximable. In this talk, I will focus on the approximability of submodular k-partition for three subfamilies of submodular functions - namely symmetric, monotone, and posimodular submodular functions. I will present the principal partition sequence based algorithm for submodular k-partition designed by Narayanan, Roy, and Patkar (1996) and sketch its approximation factor analysis for these three subfamilies of submodular functions.
Based on joint work with Weihang Wang. APPROX '23. https://arxiv.org/abs/2305.01069 .
