[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
Balas, Saltzman (1989) Facets of the three-index assignment polytope. Discrete Appl. Math. 23:201-229.
Crama, Kolen, Oerlemans, Spieksma (1990) Throughput rate optimization in the automated assembly of printed circuits boards. Ann. Oper. Res. 26:455-480.
Crama, Spieksma (1992) Approximation algorithms for three-dimensional assignment problems with triangle inequalities. European J. Oper. Res. 60:273-279.
Feo, Khellaf (1990) A class of bounded approximation algorithms for graph partitioning. Networks 20:181-195.
Frieze (1974) A bilinear programming formulation of the 3-dimensional assignment problem. Math. Programming 7:376-379.
Frieze, Yadegar (1981) An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice. Journal of the Operational Research Society 32:989-995.
Haley (1963) The Multi-Index Problem. Operations Research 11:368-379.
Hansen, Kaufman (1973) A primal-dual algorithm for the three-dimensional assignment problem. Cahiers Centre Études Rech. Opér. 15:327-336.
Karp (1972) Reducibility among combinatorial problems. Complexity of Computer Computations , R.E. Miller, J.W. Thatcher, Plenum Press, New York; 85-103.
Lengauer Combinatorial Algorithms for Integrated Circuit Layout, Wiley, New York, Teubner, Stuttgart; 1990.