Title: Cost Minimisation in Unbounded Multi-Interface Networks

Authors:

Adrian Kosowski
Department of Algorithms and System Modeling,
Gdańsk University of Technology,
Narutowicza 11/12, 80952 Gdansk, Poland.

Alfredo Navarra
Dipartimento di Matematica e Informatica,
Università degli Studi di Perugia,
Via Vanvitelli 1, 06123 Perugia, Italy.

Abstract:

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 
in order 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. 
The problem is called Cost Minimisation in Multi-Interface Networks and so far 
only the case with bounded k was studied. In this paper we generalise the model 
by considering the unbounded version of the problem, i.e., k is not set a priori 
but depends on the given instance. We distinguish two main variations 
of the problem by treating the cost of maintaining an active interface 
as uniform (i.e., the same for all interfaces), or non-uniform. 
In general, we prove that the problem is not approximable within O(log k) 
while it admits a min{ceil((k+1)/2), 2m/n}-approximation factor 
for the uniform case and a min{k-1,sqrt(n)(1+ln n)}-approximation factor 
for the non-uniform case. 
Next, we also provide hardness and approximation results for several classes 
of networks: with bounded degree, trees, planar and complete graphs.