Tradeoffs in process strategy games with application in the WDM reconfiguration problem

Nathann Cohen 1 David Coudert 1 Dorian Mazauric 1 Napoleao Nepomuceno 1, 2 Nicolas Nisse 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We consider a variant of the graph searching games that models the routing reconfiguration problem in WDM networks. In the digraph processing game, a team of agents aims at processing, or clearing, the vertices of a digraph D. We are interested in two different measures: 1) the total number of agents used, and 2) the total number of vertices occupied by an agent during the processing of D. These measures respectively correspond to the maximum number of simultaneous connections interrupted and to the total number of interruptions during a routing reconfiguration in a WDM network. Previous works have studied the problem of independently minimizing each of these parameters. In particular, the corresponding minimization problems are APX-hard, and the first one is known not to be in APX. In this paper, we give several complexity results and study tradeoffs between these conflicting objectives. In particular, we show that minimizing one of these parameters while the other is constrained is NP-complete. Then, we prove that there exist some digraphs for which minimizing one of these objectives arbitrarily impairs the quality of the solution for the other one. We show that such bad tradeoffs may happen even for a basic class of digraphs. On the other hand, we exhibit classes of graphs for which good tradeoffs can be achieved. We finally detail the relationship between this game and the routing reconfiguration problem. In particular, we prove that any instance of the processing game, i.e. any digraph, corresponds to an instance of the routing reconfiguration problem.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2011, 412 (35), pp.4675-4687. <10.1016/j.tcs.2011.05.002>
Liste complète des métadonnées
Contributeur : Dorian Mazauric <>
Soumis le : jeudi 12 mai 2011 - 16:56:38
Dernière modification le : mardi 25 octobre 2011 - 10:25:06
Document(s) archivé(s) le : vendredi 9 novembre 2012 - 11:15:58


Fichiers produits par l'(les) auteur(s)




Nathann Cohen, David Coudert, Dorian Mazauric, Napoleao Nepomuceno, Nicolas Nisse. Tradeoffs in process strategy games with application in the WDM reconfiguration problem. Theoretical Computer Science, Elsevier, 2011, 412 (35), pp.4675-4687. <10.1016/j.tcs.2011.05.002>. <inria-00592507>



Consultations de
la notice


Téléchargements du document