Abstract:
We study the problem of assigning different communication channels to acces points in a wireless Local Area Network. Each access point will be assigned a specific radio frequency channel. Since channels with similar frequencies interfere, it is desirable to assign far apart channels (frequencies) to nearby access points. Our goal is to assign the channels so as to minimize the overall interference experienced by all access points. The above problem can be formulated as an instance of the Minimum Graph Homomorphism problem. We give a complete description of all possible approximation classes for the general formulation of the problem.