Complexity and inapproximability results for the Power Edge Set problem

被引：1

作者：

Toubaline, Sonia ^{[1
,2
]}

D'Ambrosio, Claudia ^{[2
]}

Liberti, Leo ^{[2
]}

Poirion, Pierre-Louis ^{[2
]}

Schieber, Baruch ^{[3
]}

Shachnai, Hadas ^{[4
]}

机构：

[1] PSL Res Univ, Univ Paris Dauphine, CNRS, LAMSADE, F-75016 Paris, France

[2] Ecole Polytech, CNRS, LIX, F-91128 Palaiseau, France

[3] IBM TJ Watson Res Ctr, Yorktown Hts, NY 10598 USA

[4] Technion, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2018年 / 35卷 / 03期

关键词：

PMU placement problem; Power Edge Set; NP-hardness; Inapproximability; DOMINATION; GRAPHS; ALGORITHMS; HARDNESS;

D O I：

10.1007/s10878-017-0241-y

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We consider the single channel PMU placement problem called the Power Edge Set problem. In this variant of the PMU placement problem, (single channel) PMUs are placed on the edges of an electrical network. Such a PMU measures the current along the edge on which it is placed and the voltage at its two endpoints. The objective is to find the minimum placement of PMUs in the network that ensures its full observability, namely measurement of all the voltages and currents. We prove that PES is NP-hard to approximate within a factor (1.12)-, for any . On the positive side we prove that PES problem is solvable in polynomial time for trees and grids.

引用

页码：895 / 905

页数：11

共 16 条

[1] Aazami A., 2008, Hardness Results and Approximation Algorithms for Some Problems on Graphs
[2] Aazami A, 2007, LECT NOTES COMPUT SC, V4627, P1
[3] Zero forcing sets and the minimum rank of graphs
Barioli, Francesco
Barrett, Wayne
Butler, Steve
Cioaba, Sebastian M.
Cvetkovic, Dragos
Fallat, Shaun M.
Godsil, Chris
Haemers, Willem
Hogben, Leslie
Mikkelson, Rana
Narayan, Sivaram
Pryporova, Olga
Sciriha, Irene
So, Wasin
Stevanovic, Dragan
van der Holst, Hein
Vander Meulen, Kevin N.
Wehe, Amy Wangsness
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (07) : 1628 - 1648
[4] The PMU placement problem
Brueni, DJ
Heath, LS
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 19 (03) : 744 - 761
[5] On the hardness of approximating minimum vertex cover
Dinur, I
Safra, S
[J]. ANNALS OF MATHEMATICS, 2005, 162 (01) : 439 - 485
[6] A note on power domination in grid graphs
Dorfling, M
Henning, MA
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (06) : 1023 - 1027
[7] Emami R, 2008, 16 POW SYST COMP C I, P923
[8] Robust Measurement Design by Placing Synchronized Phasor Measurements on Network Branches
Emami, Roozbeh
Abur, Ali
[J]. IEEE TRANSACTIONS ON POWER SYSTEMS, 2010, 25 (01) : 38 - 43
[9] Feige U, 2003, MCS0315 WEIZM I
[10] Guo J, 2005, LECT NOTES COMPUT SC, V3623, P172

← 1 2 →