title:
SOCP relaxation in Euclidean geometry optimization
For n points in the plane, suppose m of the points are known and
the Euclidean distance between pairs of `neighboring' pts
are known. We wish to estimate the remaining n-m points.
Recently Biswas and Ye proposed an SDP relaxation for
this problem in the context of ad hoc wireless sensor network
localization.
Here we consider SOCP and mixed SOCP-SDP relaxation for the problem and
study the quality of the approximate solutions and methods for
solving the relaxations.