Constant-Approximation for Minimum Connected Dominating Set with Small Routing Cost in Wireless Sensor Networks

Title: Constant-Approximation for Minimum Connected Dominating Set with Small Routing Cost in Wireless Sensor Networks
Speaker: Ding-Zhu Du
Time: 3:30PM, June 24, 2011
Venue: Lecture Room, Level 3 Building #5, Institute of Software, CAS

Abstract: We show that given a unit disk graph, there exists a polynomial-time constant-approximation for the minimum connected dominating set under constraint that routing cost between any pair of nodes is within a factor of \alpha from the shortest one when \alpha \geq 5. This gives a positive solution to a previous open problem in wireless sensor networks.

Biography:
Ding-Zhu Du received his M.S. degree in 1982 from Institute of Applied Mathematics, Chinese Academy of Sciences, and his Ph.D. degree in 1985 from the University of California at Santa Barbara. He worked at Mathematical Sciences Research Institutea, Berkeley in 1985-86, at MIT in 1986-87, and at Princeton University in 1990-91. He was an associate-professor/professor at Department of Computer Science and Engineering, University of Minnesota in 1991-2005, a professor at City University of Hong Kong in 1998-1999, a research professor at Institute of Applied Mathematics, Chinese Academy of Sciences in 1987-2002, and a Program Director at National Science Foundation of USA in 2002-2005 and was the Dead of Science at Xi’an Jiaotong University in 2005-2008. Currently, he is a professor at Department of Computer Science, University of Texas at Dallas and WCU professor at Korea University. His research interests include combinatorial optimization, communication networks, and theory of computation. He has published more than 160 journal papers and 10 written books. He is the editor-in-chief of Journal of Combinatorial Optimization and Discrete Mathematics, Algorithms and Applications. He is also in editorial boards of more than 15 journals in computer science, mathematics and operations research. In 1998, he received CSTS Prize from INFORMS (a merge of American Operations Research Society and Institute of Management Science) for research excellence in the interface between Operations Research and Computer Science. In 1996, he received the 2nd Class National Natural Science Prize in China. In 1993, he received the 1st Class Natural Science Prize from Chinese Academy of Sciences.