Submodular cost allocation problem and applications

Chandra Chekuri, Alina Ene

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


We study the Minimum Submodular-Cost Allocation problem (MSCA). In this problem we are given a finite ground set V and k non-negative submodular set functions f 1,....,f k on V. The objective is to partition V into k (possibly empty) sets A 1,⋯, A k such that the sum ∑i=1 k f i (A i ) is minimized. Several well-studied problems such as the non-metric facility location problem, multiway-cut in graphs and hypergraphs, and uniform metric labeling and its generalizations can be shown to be special cases of MSCA. In this paper we consider a convex-programming relaxation obtained via the Lovász-extension for submodular functions. This allows us to understand several previous relaxations and rounding procedures in a unified fashion and also develop new formulations and approximation algorithms for related problems. In particular, we give a (1.5 - 1/k)-approximation for the hypergraph multiway partition problem. We also give a min {2(1 - 1/k), H Δ}- approximation for the hypergraph multiway cut problem when Δ is the maximum hyperedge size. Both problems generalize the multiway cut problem in graphs and the hypergraph cut problem is approximation equivalent to the node-weighted multiway cut problem in graphs.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
Number of pages13
EditionPART 1
StatePublished - 2011
Event38th International Colloquium on Automata, Languages and Programming, ICALP 2011 - Zurich, Switzerland
Duration: Jul 4 2011Jul 8 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6755 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other38th International Colloquium on Automata, Languages and Programming, ICALP 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Submodular cost allocation problem and applications'. Together they form a unique fingerprint.

Cite this