Approximation Algorithms for Submodular Multiway Partition
Authors:
- Chandra ChekuriCCChandra Chekuri
- Alina EneAEAlina Ene
- 1 October 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 807-816
Abstract
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 } ⊆ V of k elements called terminals, and a non-negative submodular 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 . 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 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 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. (1) A 2-approximation for SUB-MP. This improves the (k - 1)-approximation from [29]. (2) A (1.5 - 1/k)-approximation for SUB-MP when f is symmetric. This improves the 2(1 - 1/k)-approximation from [23], [29].Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Computing Minimum Multiway Cuts in Hypergraphs from Hypertree PackingsLecture Notes in Computer Science, 2010
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions2009
- Submodular Function Minimization under Covering Constraints2009
- Maximizing Submodular Set Functions Subject to Multiple Linear Constraints2009
- Rounding Algorithms for a Geometric Embedding of Minimum Multiway CutMathematics of Operations Research, 2004
- Multiway cuts in node weighted graphsJournal of Algorithms, 2004
- A lower bound of on the integrality ratio of the Călinescu–Karloff–Rabani relaxation for multiway cutInformation Processing Letters, 2000
- A Polynomial Algorithm for the k-cut Problem for Fixed kMathematics of Operations Research, 1994
- Multiway cuts in directed and node weighted graphs1994
- Submodular functions and convexity1983