3 papers
cs.DS2026
Correlation Clustering with Random Partial Information
Rajath Rao K. N., Jens Schlöter, Sami Davies +2
Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, ye…
cs.DS2026
Faster Randomized and Deterministic k-Clustering on Graphs
Sebastian Forster, Yasamin Nazari, Rajath Rao K. N. +1
In this paper, we study the -clustering and -center problems on graphs, where -clustering generalizes the -median () and -means () problems. We obt…
cs.DS2022
Parameterizing Path Partitions
Henning Fernau, Florent Foucaud, Kevin Mann +2
We study the algorithmic complexity of partitioning the vertex set of a given (di)graph into a small number of paths. The Path Partition problem (PP) has been studied extensively,…