Greedy splitting algorithms for approximating multiway partition problems

Given a system (V, T, f, k), where V is a finite set, T subset of or equal to V, f : 2(V) --> R is a submodular function and k greater than or equal to 2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition P = {V-1, V-2,..., V-k} of V that satisfies V-i boolean AND T not equal empty set for all i and minimizes f (V-1) + f (V-2)+...+ f (V-k), where P is a k-partition of V if ( i) V-i not equal empty set, (ii) V-i boolean AND V-j = empty set, i not equal j, and (iii) V-1 boolean OR V-2 boolean OR ... V-k = V hold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such as k-way cut, multiterminal cut, target split and their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs.