Approximation Algorithms for Submodular Multiway Partition

Details Approximation Algorithms for Submodular Multiway Partition Approximation Algorithms for Submodular Multiway Partition

2011-05-10

arxiv.org/abs/1105.2048v1

Computer Science

Data Structures and Algorithms

Scientific paper

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}.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for Submodular Multiway Partition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Algorithms for Submodular Multiway Partition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for Submodular Multiway Partition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-610783