2011/05/10 by Chandra Chekuri, Chekuri, Chandra, Alina Ene +1 · 3 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1105.2040
openalex publication_date 2011/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 f1 ,..., fk on V. The objective is to partition V into k (possibly empty) sets A1 ,..., Ak such that the sum ∑i=1k fi(Ai) 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 several 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.