The topology of an FDMA network is modeled by a subdivision of a planar region into hexagonal cells; this defines a graph where every node has at most six neighbors. For channel allocation, every node has a weight that indicates the number of channels that must be assigned to it; the reuse distance defines the minimum distance between nodes that can use the same channel without radio interference. It is known that with reuse distance 2, the number of channels needed and their allocation can be approximated within a factor of $4/3$ both offline and online. We describe an online algorithm for the case of reuse distance 3 that achieves an approximation factor of $7/3$.
DIMACS Home Page