Next:
Storage and Retrieval
Up:
Weighted Set Problems
Previous:
SP10 MINIMUM 3-DIMENSIONAL
-
I
NSTANCE
:
Disjoint sets
and, for any
,
, and
, a nonnegative capacity
c(x,y)
.
-
S
OLUTION
:
A system of representatives
T
, i.e., a set
T
such that, for any
i
,
.
-
M
EASURE
:
The capacity of the system of representatives, i.e.,
.
-
Bad News:
Not approximable within
for some
p>0
unless NP
[
39
].
-
Comment:
Does not admit a PTAS.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997