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

**
Speaker**: Ding-Zhu Du

**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.