Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 21, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Georg Anegg
There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models include additional covering constraints. Prior approximation results for these models require to relax some of the constraints, like the number of centers to be opened or the involved covering constraints, and therefore, only obtain pseudo-approximations. Our result introduces a new approach to deal with such covering constraints that leads to (true) approximations, including a 4-approximation for Colorful k-Center with constantly many colors---settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan---and a 4-approximation for Fair Robust k-Center, for which the existence of a (true) constant-factor approximation was also open. Joint work with Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen.
Automatic MiSe System Software Version 1.4803M | admin login