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

### MAXIMUM CAPACITY REPRESENTATIVES

- INSTANCE: Disjoint sets and, for any , , and , a nonnegative capacity c(x,y).

- SOLUTION: A system of representatives T, i.e., a set T such that, for any i, .

- MEASURE: The capacity of the system of representatives, i.e., .

- Bad News: Not approximable within for some p>0 unless NP [62].

- Comment: Does not admit a PTAS.