Complexité du problème Power Edge Set

Session : PPP-2 / Placement, Partionnement, Packing
Mercredi 10 février 15:00 - 16:00 Salle : CI2-22
Sonia Toubaline, Claudia D'Ambrosio, Leo Liberti, Pierre-Louis Poirion, Baruch Schieber et Hadas Shachnai

Nous considérons le PMU placement problem pour des PMUs avec une seule sortie, appelé le problème Power Edge Set (PES). Dans cette variante du PMU placement problem, les PMUs sont placés sur les arêtes du réseau électrique et permettent ainsi de mesurer le courant le long de cette arête et la tension à ses deux sommets extrémités. L'objectif est de déterminer le nombre minimum de PMUs à placer sur le réseau tel que ce dernier soit entièrement observable (toutes les tensions et courants sont mesurés). Nous montrons que PES est NP-difficile à approximer à un facteur (1.12)-epsilon, pour tout epsilon >0. Nous prouvons aussi que PES est polynomial pour les arbres. Pour des arbres d'ordre n, le problème est résoluble en temps O(n).

Mots clés : PMU placement problem, Power Edge Set, NP-difficulté, inapproximabilité