報告題目： Min-Max Set Cover and Group Set Cover

報告人：Dingzhu DU教授

報告時間： 2019年9月25日下午2：00

地點：旭日樓211教室

報告簡介：

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.

報告人簡介：

 Dingzhu DU教授于1982年獲中國科學院碩士學位，1985年獲美國加利福利亞大學聖巴巴拉分校博士學位。1985年～1986年在美國加州伯克利數學科學研究院做博士後，1986～1987年在美國麻省理工大學數學系做助理教授，1987年任中國科學院應用數學所研究員。1990-1991訪問 普林斯頓大學計算機科學系。1991年和1995年成為明尼蘇達大學計算機系的副教授和教授。并于2002-2005任美國國家基金委計算機理論項目主管，2005-2009任西安交通大學理學院院長。現任德克薩斯大學達拉斯分校（UTD）計算機系教授。研究方向包括組合優化，計算機網絡和計算複雜性理論。已經發表論文200多篇，出版了10本書。《離散數學、算法與應用》和《計算社交網絡》的主編，超過15個雜志的編委。1998年獲得美國INFORMS的CSTS獎，1993年獲得中國自然科學二等獎，1992年獲得中國科學院自然科學一等獎