APPROXIMATING SUBMODULAR \bfitk-PARTITION VIA PRINCIPAL PARTITION SEQUENCE

In submodular k-partition, the input is a submodular function f : 2^V \rightarrow \BbbR_\geq0 (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 nonempty parts V1, V2,..., V_k in order to minimize ^\sumk_i=1 f(Vi). Narayanan, Roy, and Patkar [J. Algorithms, 21 (1996), pp. 306-330] 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 [European J. Oper. Res., 186 (2008), pp. 77-90]). 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 [R. Santiago, Proceedings of the International Workshop on Combinatorial Algorithms, IWOCA, 2021, pp. 516-530]. 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 \Omega(n/k).