Article (Scientific journals)
Approximation algorithms for multi-dimensional assignment problems with decomposable costs
Bandelt, Hans-Jürgen; Crama, Yves; Spieksma, Frits C.R.
1994In Discrete Applied Mathematics, 49, p. 25-50
Peer Reviewed verified by ORBi
 

Files


Full Text
MultidimensionalAssignment.pdf
Publisher postprint (1.49 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Abstract :
[en] 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.
Disciplines :
Mathematics
Quantitative methods in economics & management
Author, co-author :
Bandelt, Hans-Jürgen
Crama, Yves  ;  Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production
Spieksma, Frits C.R.
Language :
English
Title :
Approximation algorithms for multi-dimensional assignment problems with decomposable costs
Publication date :
1994
Journal title :
Discrete Applied Mathematics
ISSN :
0166-218X
eISSN :
1872-6771
Publisher :
Elsevier Science, Amsterdam, Netherlands
Volume :
49
Pages :
25-50
Peer reviewed :
Peer Reviewed verified by ORBi
Commentary :
Available on Open archive
Available on ORBi :
since 21 December 2017

Statistics


Number of views
65 (4 by ULiège)
Number of downloads
96 (0 by ULiège)

Scopus citations®
 
58
Scopus citations®
without self-citations
51
OpenCitations
 
51

Bibliography


Similar publications



Contact ORBi