Transformation

suivant: Exemple monter: Transformation polynomiale du problème précédent: Définitions et notations Table des matières

Transformation

A partir d'une instance du problème de minimisation de buffers, on crée une instance de couverture de poids minimal de la sorte :

à chaque buffer $b \in \mathcal{B}$ , on associe sommets $(b, 1), \ldots, (b, k(b))$ ;
à chaque sommet , on associe un poids $v(b, i) = w_{b}(\Delta^{i}(b)-\Delta^{i-1}(b)), i=1, \ldots, k(b)$ ;
l'ensemble des sommets est formé par les sommets tels que $b \in \mathcal{B}_{12}$ , l'ensemble par les sommets tels que $b \in \mathcal{B}_{21}$ ;
pour chaque couple $(b, b^{\prime})$ , on construit une arête entre les sommets et $(b, k^{\prime})$ si il existe dans $C(b, b^{\prime })$ une clause $(\Delta(b)\geq x_{i})\vee(\Delta(b^{\prime})\geq y_{i+1})$ telle que $\Delta^{k}(b) \leq x_{i}$ et $\Delta^{k^{\prime}}(b) \leq y_{i+1}$ .

Pour chaque buffer , si la couverture prend les sommets $\{(b, 1), \ldots, (b, i)\}$ , alors le poids à donner au buffer est $\Delta^{i}(b)$ .

Selon un théorème d'Alix Munier[2], on a l'équivalence : est une couverture $\iff$ toutes les clauses sont satisfaites. Comme le poids de la couverture est proportionnel à la fonction objectif, une couverture de poids minimal nous permettra de minimiser cette fonction objectif. alors $\mathcal{C}_{\Sigma}$ est minimal aussi.

suivant: Exemple monter: Transformation polynomiale du problème précédent: Définitions et notations Table des matières

Alexandre 2009-05-14