Approximating Submodular k-Partition via Principal Partition Sequence

In submodular k-partition, the input is a submodular function f : 2^V → R_≥0 (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 V1, V2, . . ., V_k in order to minimize ^Pk_i=1 f(Vi). Narayanan, Roy, and Patkar [18] 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 (which was subsequently rediscovered by Ravi and Sinha [22]). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions – namely monotone, symmetric, and posimodular and 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 that was known to be achievable for monotone submodular k-partition via other algorithms. Moreover, our upper bound of 4/3 matches the recently shown lower bound under polynomial number of function evaluation queries [23]. Our upper bound of 4/3 is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular k-partition. 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 Ω(n/k).