K$ Center

K-center clustering aims to partition a dataset into k clusters by selecting k centers that minimize the maximum distance from any point to its nearest center. Current research focuses on developing efficient approximation algorithms for various k-center variants, including those handling imbalanced data, incorporating constraints (must-link/cannot-link), addressing outliers, and ensuring fairness across different groups. These advancements are driven by the need for robust and scalable clustering solutions in diverse applications, ranging from image analysis and vulnerability prediction to large-scale data analysis and optimization problems. The development of improved approximation algorithms and coreset constructions is a major theme, aiming to balance solution quality with computational efficiency.

Papers

August 26, 2024

Provable Imbalanced Point Clustering
David Denisov, Dan Feldman, Shlomi Dolev, Michael Segal
Choice Model K$ Center Imbalanced Clustering

January 23, 2024

Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge
Longkun Guo, Chaoqi Jia, Kewen Liao, Zhigang Lu, Minhui Xue
Data Clustering Background Knowledge Clustering Result Near Optimal Algorithm Clustering Problem K$ Center

September 2, 2023

Approximating Fair $k$-Min-Sum-Radii in $\mathbb{R}^d$
Lukas Drexler, Annika Hennes, Abhiruk Lahiri, Melanie Schmidt, Julian Wargalla
Clustering Algorithm Fair Clustering Median Problem K$ Center

July 28, 2023

Dynamic algorithms for k-center on graphs
Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos
Graph Drawing Dynamic Graph Shortest Path Classical Algorithm Dynamic Algorithm Weighted Graph K$ Center

May 12, 2023

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase
K$ Mean Robust Clustering Discrete Space K$ Center Parametric Approximation Disjoint Cluster High Dimensional Euclidean Space

April 3, 2023

OutCenTR: A novel semi-supervised framework for predicting exploits of vulnerabilities in high-dimensional datasets
Hadi Eskandari, Michael Bewong, Sabih ur Rehman
High Dimensional Outlier Detection Security Vulnerability Vulnerability Data Inherent Vulnerability Novel Semi Supervised K$ Center

January 7, 2023

Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers
Hu Ding, Ruomin Huang, Kai Liu, Haikuo Yu, Zixiu Wang
Computational Complexity Greedy Algorithm Greedy Approach Coreset Size Semi Supervised Clustering K$ Center

December 30, 2022

A Global Optimization Algorithm for K-Center Clustering of One Billion Samples
Jiayang Ren, Ningning You, Kaixun Hua, Chaojie Ji, Yankai Cao
Global Optimization External Sample Cluster Center K$ Center

June 22, 2022

Constant-Factor Approximation Algorithms for Socially Fair $k$-Clustering
Mehrdad Ghadiri, Mohit Singh, Santosh S. Vempala
Procedural Fairness K$ Mean Approximation Algorithm Constant Factor Approximation K$ Center K$ Clustering

February 16, 2022

Distributed k-Means with Outliers in General Metrics
Enrico Dandolo, Andrea Pietracaprina, Geppino Pucci
Data Clustering K Mean K$ Center Metric Driven Approach

January 7, 2022

k-Center Clustering with Outliers in Sliding Windows
Paolo Pellizzoni, Andrea Pietracaprina, Geppino Pucci
Efficient Algorithm Global Outlier Unsupervised Machine Learning Sliding Window Streaming Model K$ Center