GRASP Seminar Series: Spring 2006

March 2, 12:00 p.m., Berger Auditorium, Skirkanich Hall (210 S. 33rd Street)

Yinyu Ye
Stanford University

"A Semidefinite Programming Model for Graph Realization and Sensor Network Localization" 

Abstract: We present semidefinite programming (SDP) based approaches for the position estimation problem in Euclidean distance geometry such as graph realization and sensor network localization. We develop an SDP relaxation model and use the duality theory to derive necessary and/or sufficient conditions for whether a network is "realizable or localizable" or not, when the distance measures are accurate. We also present error analyses of the SDP solution when the distance measures are noisy. Furthermore, we develop a further relaxation such that large-scale problems can be solved efficiently, and demonstrate computational results to show the effectiveness of the SDP relaxation model.

Biography: Yinyu Ye received the B.S. degree in System Engineering from the Huazhong University of Science and Technology, Wuhan, China, and the M.S. and Ph.D. degrees in Management Science & Engineering from Stanford University. Currently, he is Professor of Management Science and Engineering and, by courtesy, Electrical Engineering, and the Director of the MS&E Industrial Affiliates Program at Stanford University. His current research interests include Mathematical Programming Algorithm, Computational Game/Market Equilibrium, Metric Distance Geometry, Graph Realization, Stochastic Combinatorial Optimization, Dynamic Resource Allocation and Decision Making.


Full Seminar schedule...

GRASP Laboratory
Site maintained by graspadm@grasp.cis.upenn.edu
Last update:11 February, 2007