(A Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems)

Sunyoung Kim, Masakazu Kojima, Hayato Waki, and Makoto Yamashita

August, 2008. Revised January, 2010

SFSDP is a Matlab package for solving sensor network localization problems. The package contains four functions, SFSDP.m, SFSDPplus.m, generateProblem.m, test_SFDP.m, and some numerical examples. The function SFSDP.m is an Matlab implementation of the semidefinite programming relaxation proposed in the paper [2] by Kim, Kojima and Waki for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) by Biswas and Ye [1]. To improve the efficiency of FSDP, SFSDP.m exploits the aggregated and correlative sparsity of a sensor network localization problem. See also [3].

[1] P. Biswas and Y. Ye, "Semidefinite programming for ad hoc wireless sensor network localization," in Proceedings of the third international symposium on information processing in sensor networks, ACM press, 46-54 (2004).

[2] S. Kim, M. Kojima, and H. Waki, "Exploiting sparsity in SDP relaxation for sensor network localization," SIAM Journal of Optimization Vol.20 (1) 192-215 (2009).

[3] S. Kim, M. Kojima, H. Waki and M. Yamashita, "SFSDP: a Sparse Version of Full Semidefinite Programming Relaxation for Sensor Network Localization Problem". ACM Transactions on Mathematical Software Vo.38, 4 (2012).

• readme.txt

• B449.pdf : User Manual

• SFSDP122.tar.gz

• SFSDP122.zip