Reproduce “Connected k-Median with Disjoint and Non-disjoint Clusters” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Jan Eube, Kelin Luo, Dorian Reineccius, Heiko Röglin, Melanie Schmidt
The paper investigates the connected k-median problem, where clusters must be connected subgraphs in a given graph and points are assigned to minimize total distance to cluster centers. It introduces an O(k^2 log n)-approximation for the non-disjoint cluster variant on general graphs and an O(n^2 k^2) exact algorithm for the disjoint cluster variant on tree graphs, while proving a strong (n^(1- ) ) inapproximability for disjoint clusters on general graphs.
Key insights
- The distinction between disjoint and non-disjoint clusters is critical for connected k-median, with disjoint clusters on general graphs proving to be severely inapproximable.
- Allowing non-disjoint (overlapping) clusters significantly improves the tractability of the connected k-median problem on general graphs, enabling the first known approximation algorithms.
- LP-rounding and Node-Weighted Steiner Tree algorithms can be effectively adapted and combined to handle the complex interplay of metric distances and connectivity constraints for approximating connected k-median.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.