Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· pp. 1196-1203· 0 citations· 33 references
TL;DR
It is shown that exact k-center becomes tractable and scalable in the small-k regime introducing a new exact algorithm that borrows concepts from LP-type optimization to obtain exact solutions for interesting classes of real-world datasets.
Abstract
k-center clustering on graphs is widely used in data mining tasks such as prototype selection, facility placement, and dataset summarization. Despite its importance, practitioners rely almost entirely on approximation algorithms or heuristics due to the perceived impracticality of exact computation. We show that exact k-center becomes tractable and scalable in the small-k regime introducing a new exact algorithm that borrows concepts from LP-type optimization to obtain exact solutions for interesting classes of real-world datasets. We provide theoretical justification and extensive experiments demonstrating the practicability of our approach. Our findings challenge the conventional assumption that exact k-center is impractical and establish a new practical regime for optimal clustering.
This work develops a parameterized approximation algorithm for Euclidean fair k-center clustering with an approximation ratio of 4.732 and designs a one-pass streaming algorithm with an approximation ratio of 4.42, outperforming the state-of-the-art ratio.
Ze-Yu Lin, Chaoqi Jia, Long-Kun Guo et al.· Proceedings of the Thirty-Fi...· 0 citations
This work exponentially improves upon the approximation ratio of an existing algo-rithm to 1 r +1, presents another novel dependent-rounding algorithm with an approximation ratio of 1 / ⌈ k 2 ⌉, and modify the initial algorithm via analytical scaling techniques to achieve an approximation factor of (1 − e − r ) /r.
Aravind Srinivasan, A. Srinivasan, Jiayi Wu· 0 citations
Experiments show that KNNG-CS achieves accuracy comparable to representative gradient-approximation coreset methods, while reducing selection time by $2.3\times$-$41.2\times$ and peak memory to $0.3\%$-$7.5\%$ of the baselines.
Yingfan Liu, Lei-Yu Zhang, Jia-Dong Xie et al.· 1 citation
Community search based on user-specified query nodes is complementary to community finding or graph clustering. Prior work in community search is divided into optimizing for external separate- ness or internal cohesiveness, which does not scale well networks of over a billion edges. We present SteinerKCore, a new scala...
Ian Chen, Hao-Tian Yi, Arun Sharma et al.· 0 citations
Triangle counting is one of the most fundamental problems in network analysis. Given the massive sizes of real-world graphs, there is a long history of small-space streaming algorithms providing accurate estimates for this problem. However, most of the results focus on estimating the total triangle count or the number...
A generic reduction is given that transforms the (sensitive) input stream into a private stream, which is a semi-coreset of the input stream, which implies that any (non-private) online clustering algorithm, run as a post-processing step, can achieve good utility for the original clustering objective.
Edith Cohen, Vadym Doroshenko, Badih Ghazi et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
