MAXIMUM CAPACITY REPRESENTATIVES

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

INSTANCE: Disjoint sets $S_1, \ldots, S_m$ and, for any $i \neq j$ , $x \in S_i$ , and $y \in S_j$ , a nonnegative capacity c(x,y).
SOLUTION: A system of representatives T, i.e., a set T such that, for any i, $\vert T \cap S_i\vert=1$ .
MEASURE: The capacity of the system of representatives, i.e., $\sum_{x,y \in T}c(x,y)$ .
Bad News: Not approximable within $2^{\theta(\log^p n)}$ for some p>0 unless NP $\subseteq \mbox{\sc Dtime}(n^{d\log^{1/\varepsilon }n})$ [67].
Comment: Does not admit a PTAS.

Viggo Kann
2000-03-20