MAXIMUM FREQUENCY ALLOCATION

• INSTANCE: Graph $G=\left(V,E\right)$, and, for each node u, a finite set $L(u) \subset Z^+$ of available frequencies and an integer $M_u$.
• SOLUTION: A frequency allocation for G, i.e., for each node u, a subset S(u) of L(u) such that, for all $u \in V$, $1\leq\vert S(u)\vert\leq M_u$, and, for all $(u,v) \in E$, $S(u) \cap S(v) = \emptyset$.
• MEASURE: The stability number of the allocation, i.e., $\sum_{u \in V}\vert S(u)\vert$.

  
  

• Good News: Approximable within 2 [369].
• Bad News: APX-complete [369].
• Comment: Reduction from MAXIMUM 3-SATISFIABILITY.