2011/05/10 by Chandra Chekuri, Chekuri, Chandra, Alina Ene +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.1105.2048
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 = \s1,s2,...,sk\ called terminals, and a non-negative submodular set function f:2V→ ℝ+ on V provided as a value oracle. The goal is to partition V into k sets A1,...,Ak such that for 1 ≤ i ≤ k, si ∈ Ai and ∑i=1k f(Ai) 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 \citeZhaoNI05. Previous algorithms were based on greedy splitting and divide and conquer strategies. In very recent work \citeChekuriE11 we proposed a convex-programming relaxation for SubMP based on the Lovász-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 \citeZhaoNI05 and (ii) A (1.5-1/k)-approximation for SubMP when f is symmetric. This improves the 2(1-1/k)-approximation from \citeQueyranne99,ZhaoNI05.