We study algorithms for the SUBMODULAR MULTIWAY PARTITION problem (SUB-MP). An instance of SUB-MP consists of a finite ground set V, a subset S = {s(1,) s(2,) ..., s(k)} subset of V of k elements called terminals, and...
详细信息
ISBN:
(纸本)9780769545714
We study algorithms for the SUBMODULAR MULTIWAY PARTITION problem (SUB-MP). An instance of SUB-MP consists of a finite ground set V, a subset S = {s(1,) s(2,) ..., s(k)} subset of V of k elements called terminals, and a non-negative submodular set function f : 2(V) -> R+ on V provided as a value oracle. T P he goal is to partition V into k sets A(1), ...., A(k) to minimize Sigma(k)(i=1) f(A(i)) such that for 1 <= i <= k, s(i) is an element of A(i). SUB-MP generalizes some well-known problems such as the MULTIWAY CUT problem in graphs and hypergraphs, and the NODE-WEIGHED MULTIWAY CUT problem in graphs. SUB-MP for arbitrary submodular 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 SUB-MP based on the Lovasz-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. A 2-approximation for SUB-MP. This improves the (k - 1)-approximation from [29]. A (1.5-1/k)-approximation for SUB-MP when f is symmetric. This improves the 2(1 - 1/k)-approximation from [23], [29].
暂无评论