Topic: Min-Max Set Cover and Group Set Cover

Speaker: Prof. Ding-zhu DU

Location: Room 211, Glorious Sun Building, Yan'an Road Campus

Time: 2019-09-25 14:00:00

Brief introduction of the speaker: Professor Ding-zhu DU received his M.S. degree from the Chinese Academy of Sciences in 1982 and his Ph.D. degree from the University of California, Santa Barbara in 1985. From 1985 to 1986, he was a postdoctoral fellow at the Mathematical Sciences Research Institute in Berkeley, California, USA. From 1986 to 1987, he was an assistant professor at the Department of Mathematics, Massachusetts Institute of Technology, USA, and in 1987, he was a researcher at the Institute of Applied Mathematics, Chinese Academy of Sciences. From 1990 to 1991, he visited the Department of Computer Science at Princeton University, and in 1991 and 1995, he became an Associate Professor and Professor in the Department of Computer Science at the University of Minnesota. From 2002 to 2005, he was the director of the National Foundation, USA for Computer Theory Program, and from 2005 to 2009, he was the dean of the College of Science at Xi'an Jiaotong University. He is currently a Professor in the Department of Computer Science at the University of Texas at Dallas (UTD). His research interests include combinatorial optimization, computer networks, and computational complexity theory. He has published more than 200 papers and 10 books. He is Editor-in-chief of Discrete Mathematics, Algorithms and Applications and Computational Social Networks, and editorial board member of more than 15 journals. He received the CSTS award from INFORMS, USA in 1998, the second prize of Natural Science of China in 1993, and the first prize of Natural Science of Chinese Academy of Sciences in 1992.

Report Overview: There are three optimization problems about set covers, the maximum coverage problem, the minimum set cover problem, and the min-max set cover problem. For all of them, the greed algorithm has the best possible performance ratio among all polynomial-time approximation. However, this is not true for group set cover. In this talk, a comparison is studied between set cover and group set cover. This comparison will explore some interesting open problems for our future research.