Next: MINIMUM K-LINK PATH IN
Up: Miscellaneous
Previous: MINIMUM ATTRACTION RADIUS FOR
  Index
- INSTANCE:
Net of hexagonal cells in which n cells
are assigned a
positive load ,
an interference radius r, and m channels .
- 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
and
is greater than 2r.
- MEASURE:
The number of satisfied request, i.e.,
.
- Good News:
Approximable within
[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.
Viggo Kann
2000-03-20