Approximating submodular $k$-partition via principle partition sequence

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 find a partition of 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)$. Narayanan, Roy, and Patkar (Journal of Algorithms, 1996) designed an algorithm for submodular $k$-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is $2$ for the special case of graph cut functions (subsequently rediscovered by Ravi and Sinha (Journal of Operational Research, 2008)). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions -- monotone, symmetric, and posimodular. We note that graph and hypergraph cut functions are symmetric submodular and moreover, both monotone submodular functions and symmetric submodular functions are posimodular submodular. We analyze the approximation factor of Narayanan, Roy, and Patkar's algorithm to show the following results: 1. The approximation factor of their algorithm for monotone submodular $k$-partition is $4/3$. This result improves on the $2$-factor achievable via other algorithms. Moreover, our upper bound of $4/3$ matches the recently shown lower bound under polynomial number of function evaluation queries (Santiago, IWOCA 2021). 2. The approximation factor of their algorithm for symmetric submodular $k$-partition is $2$. This result generalizes their approximation factor analysis beyond graph cut functions. 3. The approximation factor of their algorithm for posimodular submodular $k$-partition is $2$. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is $\Omega(n/k)$.