Given a radius \(R\in \mathbb {Z}^+\) and a set X of n points distributed within a metric space, we consider the radius-constrained k-median problem, which combines both the k-center and k-median clustering problems. In this problem, the objective is the same as that of the k-median problem, with the additional constraint that every point x in X must be assigned to a center within the given radius R. This paper proposes an approximation algorithm that achieves a bicriteria approximation ratio of \((3+\varepsilon , 7)\) by incorporating local search with a key ball structure. The algorithm constructs a keyball center set to ensure coverage of the points and iteratively refines the solution through subset swaps while satisfying feasibility conditions. Thus, this process maintains coverage while reducing costs. Compared to the state-of-the-art approximation ratio of (8, 4) based on a linear programming formulation for this problem, our approach improves the k-median ratio from 8 to \(3+\varepsilon \) , at the cost of increasing the radius ratio from 4 to 7.
