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 -