Approximating Submodular \({k}\)-Partition via Principal Partition Sequence
Karthekeyan Chandrasekaran, Weihang Wang · SIAM Journal on Discrete Mathematics · 2024
Abstract. In submodular [Formula: see text]-partition, the input is a submodular function [Formula: see text] (given by an evaluation oracle) along with a positive integer [Formula: see text], and the goal is to find a partition of the ground set [Formula: see text] into [Formula: see text] nonempty parts [Formula: see text] in order to minimize [Formula: see text]. Narayanan, Roy, and Patkar [ J. Algorithms, 21 (1996), pp. 306–330] designed an algorithm for submodular [Formula: see text]-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 [Formula: see text]-partition is [Formula: see text]. This result improves on the 2-factor that was known to be achievable for monotone submodular [Formula: see text]-partition via other algorithms. Moreover, our upper bound of [Formula: see text] 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 [Formula: see text] is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular [Formula: see text]-partition. (2) The approximation factor of their algorithm for symmetric submodular [Formula: see text]-partition is 2. This result generalizes their approximation factor analysis beyond graph cut functions. (3) The approximation factor of their algorithm for posimodular submodular [Formula: see text]-partition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is [Formula: see text].