Showing 2025Show all
2 papers · 1 filter
cs.LG2025
Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
Konstantin Makarychev, Ilias Papanikolaou, Liren Shan
We study the problem of explainable k-medians clustering introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020). In this problem, the goal is to construct a threshold dec…
cs.DS2025
SPARSE-PIVOT: Dynamic correlation clustering for node insertions
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsi…