非表示:
キーワード:
-
要旨:
The bounded $k$-median problem is to select in an undirected graph $G=(V,E)
$ a set $S$ of $k$
vertices such that the maximum distance from a vertex $v \in V$ to $S$ is at
mos
t a given bound $d$
and the average distance from vertices $V$ to $S$ is minimized. We present
random
ized
algorithms for several versions of this problem.
We also study the bounded version of the uncapacitated facility location
problem.
For this latter problem we
present extensions of known deterministic algorithms for the unbounded version,
a
nd we prove some inapproximability results.
