Next: MINIMUM 3-DIMENSIONAL ASSIGNMENT Up: Weighted Set Problems Previous: Weighted Set Problems Index

### MAXIMUM CONSTRAINED PARTITION

- INSTANCE: Finite set A and a size for each , element , and a subset .

- SOLUTION: A partition of A, i.e., a subset such that .

- MEASURE: Number of elements from S on the same side of the partition as a0.

- Bad News: Not approximable within for some [452].

- Garey and Johnson: Similar to SP12