Next: MINIMUM K-LINK PATH IN Up: Miscellaneous Previous: MINIMUM ATTRACTION RADIUS FOR Index

### MAXIMUM CHANNEL ASSIGNMENT

- INSTANCE: Net of hexagonal cells in which n cells Ci are assigned a positive load ri, an interference radius r, and m channels Fi.

- SOLUTION: A channel assignment A, i.e., a multivalued function A assigning a set of cells to a channel such that if then the distance between Ci and Cj is greater than 2r.

- MEASURE: The number of satisfied request, i.e., .

- Good News: Approximable within 1/(1-e-1) [420].

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