Abstract
In submodular kpartition, the input is a submodular function f:2^V → ℝ_{≥ 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 nonempty parts V_1, V_2, …, V_k in order to minimize ∑_{i=1}^k f(V_i). Narayanan, Roy, and Patkar [Narayanan et al., 1996] designed an algorithm for submodular kpartition 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 [R. Ravi and A. Sinha, 2008]). 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 kpartition is 4/3. This result improves on the 2factor that was known to be achievable for monotone submodular kpartition via other algorithms. Moreover, our upper bound of 4/3 matches the recently shown lower bound under polynomial number of function evaluation queries [Santiago, 2021]. 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 kpartition.
2) The approximation factor of their algorithm for symmetric submodular kpartition is 2. This result generalizes their approximation factor analysis beyond graph cut functions.
3) The approximation factor of their algorithm for posimodular submodular kpartition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is Ω(n/k).
BibTeX  Entry
@InProceedings{chandrasekaran_et_al:LIPIcs.APPROX/RANDOM.2023.3,
author = {Chandrasekaran, Karthekeyan and Wang, Weihang},
title = {{Approximating Submodular kPartition via Principal Partition Sequence}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {3:13:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18828},
URN = {urn:nbn:de:0030drops188284},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.3},
annote = {Keywords: Approximation algorithms}
}
Keywords: 

Approximation algorithms 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 