Article ID: | iaor20125339 |
Volume: | 53 |
Issue: | 1 |
Start Page Number: | 23 |
End Page Number: | 44 |
Publication Date: | Sep 2012 |
Journal: | Computational Optimization and Applications |
Authors: | Pong Ting |
Keywords: | combinatorial optimization, location |
In this paper, we strengthen the edge‐based semidefinite programming relaxation (ESDP) recently proposed by Wang, Zheng, Boyd, and Ye (SIAM J. Optim. 19:655–673, 2008) by adding lower bound constraints. We show that, when distances are exact, zero individual trace is necessary and sufficient for a sensor to be correctly positioned by an interior solution. To extend this characterization of accurately positioned sensors to the noisy case, we propose a noise‐aware version of ESDP