from "Multicasting to Groups in
Optical Networks, Integral Flow with Gains, and Balanced Set Cover"
(work by Luisa Gargano, Adele
A. Rescigno and Ugo Vaccaro)
Résumé :
Étant donnés un noeud source et une famille D de sous-ensembles de noeuds dans un réseau optique WDM, le problème de Distributions dans des Groupes (DG) consiste à trouver un ensemble de chemins de la source vers au moins un noeud de chaque sous-ensemble dans D, et une affectation de longueurs d'onde à ces chemins, telle que ceux partageant un lien optique ne reçoivent pas la même longueur d'onde. L'objectif est de minimiser le nombre total de longueurs d'onde utilisées.
Nous montrons que le problème DG est étroitement relié à plusieurs problèmes importants d'optimisation combinatoire. Ceux-ci incluent le problème de Couverture et des généralisations utiles de celui-ci, qui correspondent à DG quand le réseau est un arbre. Nous montrons également un lien entre DG et le problème de maximiser la quantité de flot entier dans un réseau de flot généralisé. À partir de l'équivalence entre les problèmes DG et Couverture, il s'en suit que DG ne peut pas être approximé à un facteur logarithmique près, à moins que NP soit inclus dans Dtime(n^{loglog n}). Nous étendons aussi ce résultat d'inapproximabilité au problème de maximiser la quantité de flot entier dans un réseau de flot généralisé.
En revanche, nous donnons un algorithme
polynomial d'approximation pour le problème DG dans les graphes
de degré maximum borné, dont le facteur d'approximation garanti
atteint la borne d'inapproximabilité. Le même résultat
d'optimalité est assuré pour nos versions généralisées
du problème de Couverture.
Abstract:
Given a source node and a family D of subsets of nodes of a WDM Optical Network, the Multicasting to Groups (MG) problem is to find a set of paths from the source to at least one node in each subset in D, and an assignment of wavelengths to paths so that paths sharing an optical link are assigned different wavelengths. The goal is to minimize the total number of used wavelengths.
We note that MG is closely related to several important combinatorial optimization problems. These include Set Cover and some useful generalizations of it, that correspond to MG when the network is a tree. We also find a connection between MG and the problem of maximizing the amount of integral flow in a generalized network. From the equivalence between MG and Set Cover it follows that unless NP is included in Dtime(n^{loglog n}), MG cannot be approximated within a logarithmic factor. We extend this inapproximability result also to the problem of maximizing the integral flow in a generalized network.
On the positive side, we give a polynomial time approximation algorithm for the MG problem that for constant degree graphs has a guaranteed approximation factor matching the non-approximability bound. The same tight approximability results also holds for versions of our generalized versions of Set Cover.