Next: MINIMUM K-LINK PATH IN
Up: Miscellaneous
Previous: MINIMUM ATTRACTION RADIUS FOR
  Index
- 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.
Viggo Kann
1999-04-22