********************************************************************
************************** Special Time/Date **************************
********************************************************************
Seminar
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
------------------------------------------------------------------------------------------
| Title | : | Theory of Semidefinite Programming for Euclidean Distance Geometry Problems |
| Speaker | : | Mr. Anthony Man-Cho So |
| Stanford University | ||
| Date | : | February 13th, 2007 (Tuesday) |
| Time | : | 12:00 noon - 13:00 p.m. |
| Venue | : | Room 513, MMW Engineering Building |
| (Engineering Building Complex Phase 2) | ||
| CUHK | ||
------------------------------------------------------------------------------------------
Abstract:
|
It is a trivial matter to see that given the
coordinates of n points in R^d, 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^d (where d is fixed) that fit those distances --- turns out to be
anything but trivial. This problem arises from many applications, e.g.,
sensor network localization and molecular conformation. Part of the
difficulty comes from the facts that the realization must lie in an
d--dimensional space, and that there may not be a unique realization. Many
heuristics have been proposed for this problem. However, they either do not
have any theoretical guarantees, or they work only for some very restricted
classes of instances. In this talk, I will introduce a semidefinite programming (SDP) based model for the problem and discuss its theoretical properties. In particular, I will show how the SDP model can be used to find a realization in the required dimension if the input instance satisfies certain uniqueness properties. Besides identifying a large class of polynomial-time realizable instances, our result has interesting implications in the rigidity theory of graphs. I will also discuss a connection between our SDP model and the theory of tensegrities in discrete geometry, and show how SDP theories can be used to provide constructive proofs for results in the latter area. |
-------------------------------------------------------------------------------------------
Biography:
| Anthony Man-Cho So is a PhD candidate in the Computer Science Department at Stanford University, working under the supervision of Professor Yinyu Ye. He received a Master of Science degree in computer science from Stanford University, and a Bachelor of Science in Engineering degree in computer science with minors in Applied and Computational Mathematics, Engineering and Management Systems, and German Language and Culture from Princeton University. His current research focuses on the interplay between optimization theory and various areas of algorithm design, such as computational geometry, stochastic optimization, combinatorial optimization, and algorithmic game theory. |
************************* ALL ARE WELCOME ************************
| Host | : | Professor Li, Duan |
| Tel | : | (852) 2609-8323 |
| : | dli@se.cuhk.edu.hk | |
| Enquiries | : | Bolin Ding or Jeffrey Xu Yu |
| : | Department of Systems Engineering and Engineering Management | |
| CUHK | ||
| Website | : | http://www.se.cuhk.edu.hk/~seg5810 |
| : | seg5810@se.cuhk.edu.hk | |
********************************************************************