Interference

Pat Morin

Let G=(V,E) be an undirected geometric graph with vertex set V={x1,…xn} in Rd. The transmission radius, ri, of a vertex, xi, is defined as the length of the longest edge incident on xi; the transmission ball, bi, is the ball of radius ri centered at xi. The interference at a vertex xi is the number of transmission balls that contain xi. The interference of G is the maximum interference over all vertices of G.

One of the goals of wireless network design is to minimize inteference: Given V⊂Rd, select edges E so that G=(V,E) is connected and has minimum interference. In this talk we will survey algorithmic, probabilistic, and hardness results on this problem.