Date Added: Nov 2011
The interference at a wireless node s can be modelled by the number of wireless nodes whose trans-mission ranges cover s. Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (equivalently, a power level) to each node such that the resulting communication graph is connected, while minimizing the maximum interference. The authors consider the model introduced by von Rickenback et al. (2005), in which each transmission range is represented by a ball and edges in the communication graph are symmetric. The problem is NP-complete in two dimensions (Buchin 2008) and no polynomial-time approximation algorithm is known.