Approximation Algorithms for Submodular Multiway Partition
Preprint
Abstract
We study algorithms for the Submodular Multiway Partition problem (SubMP). An instance of SubMP consists of a finite ground set $V$, a subset of $k$ elements $S = \{s_1,s_2,...,s_k\}$ called terminals, and a non-negative submodular set function $f:2^V\rightarrow \mathbb{R}_+$ on $V$ provided as a value oracle. The goal is to partition $V$ into $k$ sets $A_1,...,A_k$ such that for $1 \le i \le k$, $s_i \in A_i$ and $\sum_{i=1}^k f(A_i)$ is minimized. SubMP generalizes some well-known problems such as the Multiway Cut problem in graphs and hypergraphs, and the Node-weighed Multiway Cut problem in graphs. SubMP for arbitrarysubmodular functions (instead of just symmetric functions) was considered by Zhao, Nagamochi and Ibaraki \cite{ZhaoNI05}. Previous algorithms were based on greedy splitting and divide and conquer strategies. In very recent work \cite{ChekuriE11} we proposed a convex-programming relaxation for SubMP based on the Lov\'asz-extension of a submodular function and showed its applicability for some special cases. In this paper we obtain the following results for arbitrary submodular functions via this relaxation. (i) A 2-approximation for SubMP. This improves the $(k-1)$-approximation from \cite{ZhaoNI05} and (ii) A $(1.5-1/k)$-approximation for SubMP when $f$ is symmetric. This improves the $2(1-1/k)$-approximation from \cite{Queyranne99,ZhaoNI05}.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Finding minimum 3-way cuts in hypergraphsInformation Processing Letters, 2010
- Maximizing Submodular Set Functions Subject to Multiple Linear Constraints2009
- The Steiner k-Cut ProblemSIAM Journal on Discrete Mathematics, 2006
- Rounding Algorithms for a Geometric Embedding of Minimum Multiway CutMathematics of Operations Research, 2004
- Greedy splitting algorithms for approximating multiway partition problemsMathematical Programming, 2004
- Multiway cuts in node weighted graphsJournal of Algorithms, 2004
- An Improved Approximation Algorithm for MULTIWAY CUTJournal of Computer and System Sciences, 2000
- The Complexity of Multiterminal CutsSIAM Journal on Computing, 1994