Approximation algorithms for submodular multiway partition

Chandra Chekuri, Alina Ene

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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].

Original languageEnglish (US)
Title of host publicationProceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Pages807-816
Number of pages10
DOIs
StatePublished - 2011
Event2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United States
Duration: Oct 22 2011Oct 25 2011

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Country/TerritoryUnited States
CityPalm Springs, CA
Period10/22/1110/25/11

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Approximation algorithms for submodular multiway partition'. Together they form a unique fingerprint.

Cite this