A local search algorithm for radius-constrained \(k\)-median

DOI10.1007/978-981-97-2340-9_15MaRDI QIDQ6636081

Gaojie Chi, Longkun Guo

Publication date: 12 November 2024

zbMATH Keywords

approximation algorithmlocal search\(k\)-center\(k\)-median

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• A bicriteria approximation algorithm for the \(k\)-center and \(k\)-median problems
• A heuristic for the Steiner problem in graphs
• The distance-constrained matroid median problem
• The ordered \(k\)-median problem: surrogate models and approximation algorithms
• Approximating $k$-Median via Pseudo-Approximation
• Local Global Tradeoffs in Metric Embeddings
• Location Theory
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Local search heuristic for k-median and facility location problems
• Constant-factor approximation for ordered k-median
• Spanners with Slack
• An improved local search algorithm for \(k\)-median

This page was built for publication: A local search algorithm for radius-constrained \(k\)-median