Given an edge-weighted undirected connected graph \(G = (V, E, \rho , \mathcal {X}, \mathcal {Y})\) , where \(\rho : E \rightarrow \textrm{R}^{+} \cup \{ 0 \}\) is an edge-weight function, \(\mathcal {X} \subset V\) is a subset of clients, and \(\mathcal {Y} \subset V\) is a subset of candidates, and a positive integer \(k < |\mathcal {Y}|\) , the k-Supplier Problem (k SP) asks for an optimal subset of \(\mathcal {Y}\) of cardinality at most k to minimize the radius from \(\mathcal {X}\) to the subset. In this paper, we focus on the case of \(\mathcal {X} \cap \mathcal {Y} \ne \emptyset , \mathcal {X}, \mathcal {Y}\) , and consider the scenario where the shortest path distances \(d(\cdot , \cdot )\) in G satisfy a parameterized triangle inequality between \(\mathcal {X}\) and \(\mathcal {Y}\) , i.e., \(d(x, y) + d(y, z) \ge \alpha \cdot d(x, z), \forall x, y, z \in \{ u, v, w \}, x \ne y, y \ne z, z \ne x\) , where \(1 \le \alpha \le 2\) is a parameter, for any three distinct vertices, \(v, u \in \mathcal {X}\) and \(w \in \mathcal {Y}\) . We present a two-stage dual approximation algorithm ALG for the kSP with parameter triangle inequality between \(\mathcal {X}\) and \(\mathcal {Y}\) . If it stops at the end of Stage 1 then it achieves a \(\frac{2}{\alpha }\) -approximation, and if it stops at the end of Stage 2 then it achieves a \((\frac{2}{\alpha ^{2}} + \frac{1}{\alpha })\) -approximation. ALG runs in a polynomial time and the above two parameterized performance factors of it are both strictly monotonic decreasing with respect to the value of parameter \(\alpha \) . For the kSP instances with parameterized triangle inequality having \(1 < \alpha \le 2\) , it is implied by \(1 \le \frac{2}{\alpha } < 2\) and \(1 \le \frac{2}{\alpha ^{2}} + \frac{1}{\alpha } < 3\) that ALG has better approximation ratios than the previously best polynomial-time 3-approximation algorithm of Hochbaum and Shmoys (J. ACM. 33: 533–550, 1986). Furthermore, regardless of the parameterized aspect, ALG achieves a 2-approximation if it stops at the end of Stage 1 and a 3-approximation if it stops at the end of Stage 2, for the general kSP.
