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

Nathann Cohen 1 David Coudert 1 Dorian Mazauric 1, 2 Napoleao Nepomuceno 1 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
2 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We consider a variant of the graph searching games that is closely related to the routing reconfiguration problem in WDM networks. In the digraph processing game, a team of agents is aiming at clearing, or processing, the vertices of a digraph D. In this game, two important measures arise: 1) the total number of agents used, and 2) the total number of vertices occupied by an agent during the processing of D. Previous works have studied the problem of minimizing each of these parameters independently. In particular, both of these optimization problems are not in APX. In this paper, we study the tradeoff between both these conflicting objectives. More precisely, we prove that there exist some instances 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 in the case of basic network topologies. On the other hand, we exhibit classes of instances where good tradeoffs can be achieved. We also show that minimizing one of these parameters while the other is constrained is not in APX.
Type de document :
Communication dans un congrès
Paola Boldi and Luisa Gargano. Fifth International conference on Fun with Algorithms (FUN 2010), Jun 2010, Ischia, Italy. Springer, 6099, pp.121-132, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13122-6_14〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00495443
Contributeur : David Coudert <>
Soumis le : samedi 26 juin 2010 - 12:07:54
Dernière modification le : mercredi 14 décembre 2016 - 01:06:06
Document(s) archivé(s) le : lundi 22 octobre 2012 - 14:51:15

Fichier

fun45.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Nathann Cohen, David Coudert, Dorian Mazauric, Napoleao Nepomuceno, Nicolas Nisse. Tradeoffs in process strategy games with application in the WDM reconfiguration problem. Paola Boldi and Luisa Gargano. Fifth International conference on Fun with Algorithms (FUN 2010), Jun 2010, Ischia, Italy. Springer, 6099, pp.121-132, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13122-6_14〉. 〈inria-00495443〉

Partager

Métriques

Consultations de la notice

372

Téléchargements de fichiers

98