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 $k(b)$ sommets $(b, 1), \ldots, (b, k(b))$;
• à chaque sommet $(b, k(b))$, on associe un poids $v(b, i) = w_{b}(\Delta^{i}(b)-\Delta^{i-1}(b)), i=1, \ldots, k(b)$;
• l'ensemble $A$ des sommets est formé par les sommets $(b, i)$ tels que $b \in \mathcal{B}_{12}$, l'ensemble $B$ par les sommets $(b, i)$ tels que $b \in \mathcal{B}_{21}$;
• pour chaque couple $(b, b^{\prime})$, on construit une arête entre les sommets $(b, k)$ 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 $b$, si la couverture prend les sommets $\{(b, 1), \ldots, (b, i)\}$, alors le poids à donner au buffer $b$ est $\Delta^{i}(b)$.

Selon un théorème d'Alix Munier[2], on a l'équivalence : $D$ 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.