Next:
SP11 MAXIMUM CAPACITY
Up:
Weighted Set Problems
Previous:
SP9 MAXIMUM CONSTRAINED
-
I
NSTANCE
:
Three sets
X
,
Y
, and
W
and a cost function
.
-
S
OLUTION
:
An assignment
A
, i.e., a subset
such that
every element of
belongs to exactly one triple in
A
.
-
M
EASURE
:
The cost of the assignment, i.e.,
.
-
Bad News:
Not in A
PX
[
84
].
-
Comment:
The negative result holds even if
c
is either defined as
c(x,y,w) = d(x,y)+d(x,w)+d(y,w)
or defined as
where
d
is any distance function. In these cases, however, the
problem is approximable within 4/3 if
d
satisfies the triangle inequality.
Similar results hold for the
k
-dimensional problem [
34
].
-
Garey and Johnson:
Weighted version of SP2
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997