Cost minimization in wireless networks with a bounded and unbounded number of interfaces

Given a graph G = ( V , E ) with | V | = n and | E | = m , which models a set of wireless devices (nodes V ) connected by multiple radio interfaces (edges E ), the aim is to switch on the minimum cost set of interfaces at the nodes to satisfy all the connections. A connection is satisfied when the endpoints of the corresponding edge share at least one active interface. Every node holds a subset of all the possible k interfaces. Depending on whether k is a priori bounded or not, the problem is called Cost Minimization in Multi‐Interface Networks or Cost Minimization in Unbounded Multi‐Interface Networks, respectively. We distinguish two main variations for both problems by treating the cost of maintaining an active interface as uniform (i.e., the same for all interfaces), or nonuniform. For bounded k , we show that the problem is APX‐hard while we obtain an approximation factor of min ${\{\lceil {k + 1 \over 2} \rceil, {2m \over n}}\}$ for the uniform caseand a ( k − 1)‐approximation for the nonuniform case. For unbounded k , i.e., k is not set a priori but depends on the given instance, we prove that the problem is not approximable within O (log k ) while the same approximation factor of the k ‐bounded case holds in the uniform case, and a min $\{k-1, \, \sqrt{n} \, {(1 + {\rm In} \, n)} \}$ ‐approximation factor holds for the nonuniform case. Next, we also provide hardness and approximation results for several classes of networks: with bounded degree, trees, planar, and complete graphs. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009