MAXIMUM CHANNEL ASSIGNMENT

• INSTANCE: Net of hexagonal cells in which n cells $C_i$ are assigned a positive load $r_i$, an interference radius r, and m channels $F_i$.

• SOLUTION: A channel assignment A, i.e., a multivalued function A assigning a set of cells to a channel such that if $C_i,C_j \in A(F_k)$ then the distance between $C_i$ and $C_j$ is greater than 2r.

• MEASURE: The number of satisfied request, i.e., $\sum_i\min\{r_i,\vert\{F_j:C_i \in F_j\}\vert\}$.

  
  

• Good News: Approximable within $1/(1-e^{-1})$ [443].

• Comment: Admits a PTAS if the number of channels is fixed. Similar results hold in the case in which each cell has a set of forbidden channels.