Random Cuts are Optimal for Explainable k-Medians

K. Makarychev, Liren Shan
2/12/2026

No confident code implementation found for this paper.

Abstract

We show that the RandomCoordinateCut algorithm gives the optimal competitive ratio for explainable k-medians in l1. The problem of explainable k-medians was introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian in 2020. Several groups of authors independently proposed a simple polynomial-time randomized algorithm for the problem and showed that this algorithm is O(log k loglog k) competitive. We provide a tight analysis of the algorithm and prove that its competitive ratio is upper bounded by 2ln k +2. This bound matches the Omega(log k) lower bound by Dasgupta et al (2020).

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds

75% match2024

Faster and Simpler Greedy Algorithm for k-Median and k-Means

75% match2024

Learning in Prophet Inequalities with Noisy Observations

75% match2026

Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search

74% match2026

Barely Random Algorithms and Collective Metrical Task Systems

74% match2026

Finding good policies in average-reward Markov Decision Processes without prior knowledge

74% match2026

Cite this paper

@article{makarychev2026random,
  title  = {Random Cuts are Optimal for Explainable k-Medians},
  author = {K. Makarychev and Liren Shan},
  year   = {2026},
  eprint = {2304.09113},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/pdf/2304.09113},
  journal = {NEURIPS 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2304.09113.svg)](https://codeofpaper.com/paper/2304.09113)

Discussion