SIAM Journal on Optimization · 2008 · 174 citations · 31 references
ComputingComputer ScienceDistributed SystemsOptimizationSensorsConvex OptimizationInteger ProgrammingMatrix ComputationNetwork OptimizationSensor NetworksWireless Sensor NetworksAccuracyConvex RelaxationsSemidefinite ProgrammingSemidefinite Programming RelaxationSemidefinite RelaxationSensor LocalizationSensor Network LocalizationWireless Sensor Network Localization
Recently, a semidefinite programming (SDP) relaxation approach has been proposed to solve the sensor network localization problem. Although it achieves high accuracy in estimating the sensor locations, the speed of the SDP approach is not satisfactory for practical applications. In this paper we propose methods to further relax the SDP relaxation, more precisely, to relax the single semidefinite matrix cone into a set of small-size semidefinite submatrix cones, which we call a sub-SDP (SSDP) approach. We present two such relaxations. Although they are weaker than the original SDP relaxation, they retain the key theoretical property, and numerical experiments show that they are both efficient and accurate. The speed of the SSDP is even faster than that of other approaches based on weaker relaxations. The SSDP approach may also pave a way to efficiently solving general SDP problems without sacrificing the solution quality.
31
Fastest Mixing Markov Chain on a Graph
Stephen Boyd, Persi Diaconis, Lin Xiao · SIAM Review · 2004 · 761 citations
Semidefinite programming for ad hoc wireless sensor network localization
Pratik K. Biswas, Yinyu Ye · 2004 · 572 citations