such that every
element in
S
belongs to at least one member of
C'
.
[
194
].
[
327
].
Not approximable within
for any
,
unless NP
[
103
].
Equivalent to M
INIMUM
D
OMINATING
S
ET
under L-reduction and equivalent to
M
INIMUM
H
ITTING
S
ET
[
27
].
If it is NP-hard to approximate within
, then it is complete
for the class of
-approximable problems [
217
].
Variation in which the subsets have positive weights and the objective is
to minimize the sum of the weights in a set cover is also approximable
within
[
77
].
The problem M
INIMUM
K
-S
ET
C
OVER
, the variation in which the cardinality of
all sets in
C
are bounded from above by a constant
k
is A
PX
-complete and is approximable, for any
, within 1.4
for
k=3
and
for
k>3
[
153
].
Variation in which the number of occurrences in
C
of
any element is bounded by a constant
B
is A
PX
-complete [
284
] and approximable within
B
even for the weighted
problem [
166
].
If, moreover, each element needs to be covered by at least
K
sets with
K
constant, this variation is approximable within
B-K+1
[
288
].
It is approximable within 2 if the set system
(S,C)
is tree representable
[
126
].
The constrained variation in which the input is extended with a positive
integer
k
and a subset
T
of
C
, and the problem is to find the set
cover of size
k
that contains the largest number of subsets from
T
,
is not approximable within
for some
[
352
].
Variation in which a distance matrix between pairs of elements in
S
is
given and the measure of the solution is not the cardinality of the cover
but its diameter (i.e., the maximum distance of any pair of elements in
C'
) is not approximable within any constant in the general case. If the
distance matrix satisfies the triangle inequality then this variation can
be approximated within 2 and no better approximation is possible. Similar
results hold if the cover can be partitioned into clusters and the goal is
to minimize the maximum diameter over all clusters [
15
] (see
also M
INIMUM
K
-C
LUSTERING
).
Viggo Kann