MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTETradeoffs in Digraph Process Strategy Game
par Dorian Mazauric
| Date : | 20/04/10 | | Time : | 10 heures | | Location : | "a determiner" |
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.
Page des séminaires
| 
