Computer Science – Data Structures and Algorithms
Scientific paper
2011-05-10
Computer Science
Data Structures and Algorithms
Extended abstract to appear in Proceedings of ICALP, July 2011
Scientific paper
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 $\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\'asz-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_{\Delta}\}$-approximation for the hypergraph multiway cut problem when $\Delta$ 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.
Chekuri Chandra
Ene Alina
No associations
LandOfFree
Submodular Cost Allocation Problem and Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Submodular Cost Allocation Problem and Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Submodular Cost Allocation Problem and Applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-610659