MAXIMUM CAPACITY REPRESENTATIVES

• 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.