Complexity and inapproximability results for the Power Edge Set problem

Sonia Toubaline (), Claudia D’Ambrosio (), Leo Liberti (), Pierre-Louis Poirion (), Baruch Schieber () and Hadas Shachnai ()
Additional contact information
Sonia Toubaline: CNRS, LAMSADE
Claudia D’Ambrosio: CNRS LIX, Ecole Polytechnique
Leo Liberti: CNRS LIX, Ecole Polytechnique
Pierre-Louis Poirion: CNRS LIX, Ecole Polytechnique
Baruch Schieber: IBM T.J. Watson Research Center
Hadas Shachnai: Technion

Journal of Combinatorial Optimization, 2018, vol. 35, issue 3, No 13, 895-905

Abstract: Abstract 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)- $$\epsilon $$ ϵ , for any $$\epsilon > 0$$ ϵ > 0 . On the positive side we prove that PES problem is solvable in polynomial time for trees and grids.

Keywords: PMU placement problem; Power Edge Set; NP-hardness; Inapproximability (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0241-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:35:y:2018:i:3:d:10.1007_s10878-017-0241-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0241-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().