Greedy splitting algorithms for approximating multiway partition problems

Given a system (V,T,f,k), where V is a finite set, is a submodular function and k2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition ={V₁,V₂,...,V_k} of V that satisfiesfor all i and minimizes f(V₁)+f(V₂)+···+f(V_k), where is a k-partition of 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.Mathematics Subject Classification (1991): 20E28, 20G40, 20C20Acknowledgement This research is partially supported by the Scientific Grant-in-Aid from Ministry of Education, Science, Sports and Culture of Japan. The authors would like to thank the anonymous referees for their valuable comments and suggestions.