An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors (Q1026115)

Let \(G\) be a complete \(k\)-partite graph where all the parts have the same cardinality and every edge has assigned a weight. Then the \(k\)-dimensional assignment problem asks to find a partition of the vertex set of \(G\) into a set of pairwise disjoint \(k\)-cliques that minimizes the total sum of edge weights of the chosen cliques. (When \(k=2\) one gets the classical assignment problem solvable by the Hungarian method.) Additionally, the authors assume that \(G\) is embedded in an Euclidean space and the weight of an edge \((u,v)\) is the square of the distance between \(u\) and \(v\). They show how such a problem arises from a multidimensional Gaussian model of a data-association problem. A second-order cone programming relaxation of the \(k\)-assignment problem and a polynomial time randomized rounding procedure are presented. This yields an expected objective value bound \((5/2-3/k)\) of the approximation ratio which improves a known bound of \textit{H. J. Bandelt, Y. Crama} and \textit{F. C. R. Spieksma} [Discrete Appl. Math. 49, No. 1--3, 25--50 (1994; Zbl 0799.90077)].