Approximation algorithms for submodular multiway partition

We study algorithms for the Sub modular Multiway Partition problem (SubMP). An instance of SubMP consists of a finite ground set V, a subset S = {s ₁s ₂,...,s _k} ⊆ V of k elements called terminals, and a non-negative sub modular set function f:2 ^V → ℝ ₊ on V provided as a value oracle. The goal is to partition V into k sets A ₁,...,A _k to minimize ∑ _i=1 ^k f(A _i) such that for 1 ≤ i ≤ k, s _i ∈ A _i. SubMP generalizes some well-known problems such as the Multiway Cut problem in graphs and hyper graphs, and the Node-weighed Multiway Cut problem in graphs. SubMP for arbitrary sub modular functions (instead of just symmetric functions) was considered by Zhao, Nagamochi and Ibaraki [29]. Previous algorithms were based on greedy splitting and divide and conquer strategies. In recent work [5] we proposed a convex-programming relaxation for SubMP based on the Lovász-extension of a sub modular function and showed its applicability for some special cases. In this paper we obtain the following results for arbitrary sub modular functions via this relaxation. • A 2-approximation for SubMP. This improves the (k-1)-approximation from [29]. • A (1.5-1/k-approximation for SubMP when f is symmetric. This improves the 2(1-1/k)-approximation from [23], [29].