Reference : Approximation algorithms for multi-dimensional assignment problems with decomposable costs |

Scientific journals : Article | |||

Business & economic sciences : Quantitative methods in economics & management Physical, chemical, mathematical & earth Sciences : Mathematics | |||

http://hdl.handle.net/2268/217331 | |||

Approximation algorithms for multi-dimensional assignment problems with decomposable costs | |

English | |

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. [] | |

1994 | |

Discrete Applied Mathematics | |

Elsevier Science | |

49 | |

25-50 | |

Yes (verified by ORBi) | |

0166-218X | |

Amsterdam | |

The Netherlands | |

[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. | |

Researchers | |

http://hdl.handle.net/2268/217331 | |

http://www.sciencedirect.com/journal/discrete-applied-mathematics/vol/49 | |

Available on Open archive |

File(s) associated to this reference | ||||||||||||||

| ||||||||||||||

All documents in ORBi are protected by a user license.