On generalized greedy splitting algorithms for multiway partition problems Original Research Article

Given a system (V,T,f,k) where V is a finite set, T⊆V, f:2V→R is a submodular function and k⩾2 is an integer, the multiway partition problem (MPP) asks to find a k-partition P={V1,V2,…,Vk} of V that satisfies Vi∩T≠∅ for all i and minimizes f(V1)+f(V2)+⋯+f(Vk). This formulation captures a generalization of many NP-hard partition problems in graphs or hypergraphs. Previously, the authors have shown a simple framework for approximating MPPs by greedily increasing the size of partition by one. In this paper, we show that, if T=V, improved guarantees are available by greedily increasing the size by two. We also show polynomial time implementations for several problem classes.