Learning-augmented approximation algorithms for group fair k-center clustering

Graphical abstract

References

[1] Gonzalez T F . Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 1985, 38: 293–306

[2] Hochbaum D S, Shmoys D B . A best possible heuristic for the k-center problem. Mathematics of Operations Research, 1985, 10( 2): 180–184

[3] Hsu W L, Nemhauser G L . Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1979, 1( 3): 209–215

[4] Chierichetti F, Kumar R, Lattanzi S, Vassilvitskii S. Fair clustering through fairlets. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017, 5036−5044

[5] Ergun J C, Feng Z, Silwal S, Woodruff D, Zhou S. Learning-augmented k-means clustering. In: Proceedings of the 10th International Conference on Learning Representations. 2022

[6] Nguyen T D, Chaturvedi A, Nguyen H L. Improved learning-augmented algorithms for k-means and k-medians clustering. In: Proceedings of the 11th International Conference on Learning Representations. 2023

[7] Bercea I O, Groß M, Khuller S, Kumar A, Rösner C, Schmidt D R, Schmidt M. On the cost of essentially fair clusterings. In: Proceedings of the 23rd Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 2019, 18:1−18:22

RIGHTS & PERMISSIONS

Higher Education Press