Next:
MINIMUM 3-DIMENSIONAL ASSIGNMENT
Up:
Weighted Set Problems
Previous:
Weighted Set Problems
 
Index
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
[
476
].
Garey and Johnson:
Similar to SP12
Viggo Kann
2000-03-20