APPROXIMATION ALGORITHMS FOR MULTIDIMENSIONAL ASSIGNMENT PROBLEMS WITH DECOMPOSABLE COSTS

The k-dimensional assignment problem with decomposable costs is formul ated as follows. Given is a complete k-partite graph G = (X0 or ... or X(k-1), E), with \X(i)\ = p for each i, and a nonnegative length func tion 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 fun ction of the lengths of the edges induced by the clique. Four specific cost functions are considered in this paper; namely, the cost of a cl ique is either the sum of the lengths of the edges induced by the cliq ue (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 (tr ee costs) of the induced subgraph. The problem is to find a minimum-co st partition of the vertex set of G into cliques. We propose several s imple heuristics for this problem, and we derive worst-case bounds on the ratio between the cost of the solutions produced by these heuristi cs and the cost of an optimal solution. The worst-case bounds are stat ed in terms of two parameters, viz. k and tau, where the parameter tau indicates how close the edge length function comes to satisfying the triangle inequality.