A
Semidefinite Programming Approach to the Graph
Realization Problem
By

Professor
Anthony ManCho So

Department
of Systems Engineering & Engineering
Management

The
Chinese University of Hong Kong

Date:
Nov 28, 2007 
Time:
3:30pm  4:30 pm 
Venue:
Rm. 1009 William MW Mong Engineering Building,
CUHK 
Abstract
:
It
is a trivial matter to see that given the coordinates
of n points in R^k, the distance between any two points
can be computed efficiently. However, the inverse
problem  given a subset of interpoint distances,
find the coordinates of points (called a realization)
in R^k (where k>=1 is fixed) that fit those distances
 turns out to be anything but trivial. In fact,
this problem has been shown to be NPhard for any
fixed k>=1. On the other hand, this problem arises
from many applications, e.g., surveying, satellite
ranging, sensor network localization and molecular
conformation, just to name a few. Thus, many heuristics
have been proposed. However, they either do not have
any theoretical guarantees, or they work only for
some very restricted classes of instances.
Recently,
Biswas and Ye (2004) have proposed a semidefinite
programming (SDP) based model for the problem and
have reported its superb experimental performance.
Our work is motivated by the desire to explain this
phenomenon in a rigorous manner. We show that the
SDP model can be used to find a realization in the
required dimension if the input instance satisfies
certain uniqueness property. This uniqueness property
has a straightforward geometric interpretation, and
it allows us to identify a large class of efficiently
realizable instances. Furthermore, it allows us to
make some interesting connections with various notions
in the rigidity theory of graphs. We then show how
ideas from the theory of tensegrities can be used
to enhance the SDP model, which in turn allows us
to design efficient heuristics for the Graph Realization
Problem.
