Interference

Pat Morin

Let G=(V,E) be an undirected geometric graph with vertex set V={x₁,…x_n} in R^d. The transmission radius, r_i, of a vertex, x_i, is defined as the length of the longest edge incident on x_i; the transmission ball, b_i, is the ball of radius r_i centered at x_i. The interference at a vertex x_i is the number of transmission balls that contain x_i. 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⊂R^d, 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.