Idée Générale

Comme l'indique la figure 3.1, le problème de départ subit des transformations successives pour nous fournir une instance d'un problème de flots :

Figure 3.1: Transformations successives du problème sur les buffers vers un problème de flots

L'étude des circuits permet de transformer le problème d'origine en une suite de clauses logiques dans lesquelles les dimensions $\{\Delta(b) \mid b \in \mathcal{B}\}$ des buffers sont des variables libres. Le but devient donc de trouver une interprétation de $\Delta$ satisfaisant toutes ces clauses tout en minimisant $\mathcal{C}_{\Sigma}$, ce qui se réduit à un problème de couverture de poids minimal d'un graphe. La couverture ainsi obtenue nous donne les valuations des variables libres et par conséquent les capacités à donner aux buffers.

Bien que le problème de la couverture de poids minimal soit NP-Complet, il existe un algorithme polynomial permettant de traiter le cas particulier dans lequel le graphe est biparti (ce qui est le cas ici). Cela se fait en réduisant ce problème de couverture de poids minimal à un problème de coupe minimale dans un réseau de transport. Un algorithme de flots nous permet d'abord de récupérer, par l'intermédiaire de la coupe, cette couverture de poids minimal, et ensuite d'en déduire les capacités à attribuer aux buffers pour minimiser la surface occupée par ces derniers.