Abstract of Talk
Connected Dominating Set in Wireless Networks
-Ding-Zhu Du
Abstract: The connected dominating set plays an important role in wireless
networks and hence gains a lot of attention in approximation algorithm
design. In this talk, we study greedy approximations for
computing the minimum connected dominating set and solution for an
long-standing open problem in greedy algorithm design and analysis.
The main result comes from a recent paper of Du, Graham, Pardalos, Wan, Wu and zhao, which will appear in SODA'08.
Biography: Dr. Ding-Zhu Du recently joined UT Dallas after being a Program Director
at National Science Foundation 2002-2005. He was a professor at Department of Computer Science and Engineering, University of Minnesota 1991-2005.
Dr. 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 Institute, Berkeley in 1985-86,
at MIT in 1986-87, and at Princeton University in 1990-91, and 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.
Currently, he is a professor at Department of Computer Science,
University of Texas at Dallas and the Dean of Science
at Xi'an Jiaotong University. His research interests include
combinatorial optimization, communication networks, and theory of computation.
He has published more than 140 journal papers and 10 written books.
He is the editor-in-chief of Journal of Combinatorial Optimization and book series on Network Theory and Applications. He is also in editorial boards of more than 15
journals. He is well-known for proving the Gilbert-Pollak conjecture
on the Steiner ratio, the Derman-Leiberman-Ross conjecture on
optimal consecutive 2-out-of-$n$ systems in reliability, and the global
convergence of Rosen gradient projection method in nonlinear programming.
In 1998, he received 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.