An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors
type: Item
instance of: scholarly article
title: An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors
zbMATH Open document ID: 1170.90010
author: Yusuke Kuroki
author: Tomomi Matsui
published in: Discrete Applied Mathematics
publication date: 2009-06-24T00:00:00Z
review text: 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)].
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5569444
zbMATH Keywords: multidimensional assignment problem
zbMATH Keywords: approximation algorithm
zbMATH Keywords: second-order cone programming
zbMATH Keywords: data-association problem
MaRDI profile type: Publication
full work available at URL: j.dam.2007.10.013
OpenAlex ID: W2029744427
cites work: Second-order cone programming
cites work: On multi-index assignment polytopes
cites work: Approximation algorithms for multi-dimensional assignment problems with decomposable costs
cites work: Local search heuristics for multi-index assignment problems with decomposable costs
cites work: Q5834711
cites work: On clustering problems with connected optima in Euclidean spaces
cites work: Three-dimensional axial assignment problems with decomposable cost coefficients
cites work: Q3145800
cites work: Geometric clusterings
cites work: Throughput rate optimization in the automated assembly of printed circuit boards
cites work: Approximation algorithms for three-dimensional assignment problems with triangle inequalities
cites work: An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice
cites work: Q4198056
cites work: The Multi-Index Problem
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Q5817856
cites work: Randomized parallel algorithms for the multidimensional assignment problem
cites work: Q5528346
cites work: Letter to the Editor—The Multidimensional Assignment Problem
cites work: Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
cites work: Q4321562
cites work: Some assignment problems arising from multiple target tracking
cites work: Statistical matching. A frequentist theory, practical applications, and alternative Bayesian approaches
cites work: Geometric three-dimensional assignment problems
cites work: Q4801573
cites work: An LP-based algorithm for the data association problem in multitarget tracking.
DOI: 10.1016/J.DAM.2007.10.013
Recommended article: Clustering for edge-cost minimization (extended abstract)
Recommended article: Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space
Recommended article: A randomized algorithm for two-cluster partition of a set of vectors
Recommended article: Polynomial-time approximation schemes for geometric min-sum median clustering
Recommended article: Linear-time approximation schemes for clustering problems in any dimensions
Recommended article: Clustering large graphs via the singular value decomposition
Recommended article: A randomized algorithm for a sequence 2-clustering problem
Recommended article: Q3115255
Recommended article: Efficient Randomized Algorithm for a Vector Subset Problem
Recommended article: On random multi-dimensional assignment problems
description: scientific article; zbMATH DE number 5569444