Constant-factor approximation for ordered k-median

DOI10.1145/3188745.3188930zbMath1427.68366arXiv1711.01972OpenAlexW2767369866MaRDI QIDQ5230325

Joachim Spoerhase, Jaroslaw Byrka, Krzysztof Sornat

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.01972

zbMATH Keywords

clusteringapproximation algorithms\(k\)-center\(k\)-median

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (6)

Approximation algorithms for clustering with dynamic points ⋮ Unnamed Item ⋮ Tight approximation algorithms for ordered covering ⋮ Simpler and Better Algorithms for Minimum-Norm Load Balancing ⋮ Reverse greedy is bad for \(k\)-center ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms

This page was built for publication: Constant-factor approximation for ordered k-median