Approximation algorithms for multi-dimensional assignment problems with decomposable costs

The k-dimensional assignment problem with decomposable costs is formulated as follows.
Given is a complete k-partite graph G = (X_0 U ... U X_{k-1}, E), with lX_il = p for each i, and
a nonnegative length function defined on the edges of G. A clique of G is a subset of vertices
meeting each X_i in exactly one vertex. The cost of a clique is a function of the lengths of the
edges induced by the clique. Four specific cost functions are considered in this paper; namely,
the cost of a clique is either the sum of the lengths of the edges induced by the clique (sum costs),
or the minimum length of a spanning star (star costs) or of a traveling salesman tour (tour costs)
or of a spanning tree (tree costs) of the induced subgraph. The problem is to find a minimumcost
partition of the vertex set of G into cliques. We propose several simple heuristics for this
problem, and we derive worst-case bounds on the ratio between the cost of the solutions
produced by these heuristics and the cost of an optimal solution. The worst-case bounds are
stated in terms of two parameters, viz. k and z, where the parameter z indicates how close the
edge length function comes to satisfying the triangle inequality.