TY - GEN

T1 - Approximation algorithms for submodular multiway partition

AU - Chekuri, Chandra

AU - Ene, Alina

PY - 2011

Y1 - 2011

N2 - 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 1s 2,...,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 1,...,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].

AB - 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 1s 2,...,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 1,...,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].

UR - http://www.scopus.com/inward/record.url?scp=84863308335&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863308335&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2011.34

DO - 10.1109/FOCS.2011.34

M3 - Conference contribution

AN - SCOPUS:84863308335

SN - 9780769545714

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 807

EP - 816

BT - Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

Y2 - 22 October 2011 through 25 October 2011

ER -