Krysta, Piotr; Solis-Oba, Roberto Approximation algorithms for bounded facility location problems. (English) Zbl 1001.90045 J. Comb. Optim. 5, No. 2, 233-247 (2001). Summary: The bounded \(k\)-median problem is to select in an undirected graph \(G=(V,E)\) a set \(S\) of \(k\) vertices such that the distance from any vertex \(v\in V\) to \(S\) is at most a given bound \(d\) and the average distance from vertices \(V\setminus S\) to \(S\) is minimized. We present randomized algorithms for several versions of this problem and we prove some inapproximability results. We also study the bounded version of the uncapacitated facility location problem and present extensions of known deterministic algorithms for the unbounded version. Cited in 4 Documents MSC: 90B85 Continuous location 90C59 Approximation methods and heuristics in mathematical programming Keywords:facility location; approximation algorithms; randomized algorithms; clustering PDF BibTeX XML Cite \textit{P. Krysta} and \textit{R. Solis-Oba}, J. Comb. Optim. 5, No. 2, 233--247 (2001; Zbl 1001.90045) Full Text: DOI