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.