Given a system (
V,
T,
f,
k), where
V is a finite set,
is a submodular function and
k
2 is an integer, the general
multiway partition problem (MPP) asks to find a
k-partition
={
V1,
V2,...,
Vk} of
V that satisfies
for all
i and minimizes
f(
V1)+
f(
V2)+···+
f(
Vk), 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.
Keywords Approximation algorithm - Hypergraph partition - k-way cut - Multiterminal cut - Multiway partition problem - Submodular function
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.