Next:
SP10 MINIMUM 3-DIMENSIONAL
Up:
Weighted Set Problems
Previous:
Weighted Set Problems
SP9 M
AXIMUM
C
ONSTRAINED
P
ARTITION
I
NSTANCE
: Finite set
A
and a size
for each
, element
, and a subset
.
S
OLUTION
: A partition of
A
, i.e., a subset
such that
.
M
EASURE
: Number of elements from
S
on the same side of the partition as
.
Bad News:
Not approximable within
for some
[
352
].
Garey and Johnson:
Similar to SP12
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
for each
, element
, and a subset
.
such that
.
.
for some
[
352
].