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

Given a complete kk-partite graph G=(V1,V2,…,Vk;E)G=(V1,V2,…,Vk;E) satisfying |V1|=|V2|=⋯=|Vk|=n|V1|=|V2|=⋯=|Vk|=n and weights of all  kk-cliques of GG, the  kk-dimensional assignment problem finds a partition of vertices of GG into a set of (pairwise disjoint) nn kk-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of GG are embedded in the dd-dimensional space QdQd and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem.We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2−3/k)(5/2−3/k) times the optimal value. Our result improves the previously known bound (4−6/k)(4−6/k) of the approximation ratio.