D ' Gianlorenzo
email: gianlorenzo.dangelo@inria.fr

Gabriele Di Angelo
email: gabriele.distefano@univaq.it

Alfredo Stefano

Navarra

G D'angelo

G Di

A Navarra

Flow problems in multi-interface networks

Keywords: Multi-Interface Networks, Flow, Computational complexity, Approximation algorithms, Experimental analysis

In heterogeneous networks, devices communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available ones, each device might establish several connections. A connection may be established when the devices at its endpoints share at least one active interface.

In this paper, we consider two fundamental optimization problems. In the first one (Maximum Flow in Multi-Interface Networks, MFMI), we aim to establish the maximal bandwidth that can be guaranteed between two given nodes of the input network. In the second problem (Minimum-Cost Flow in Multi-Interface Networks, MCFMI), we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth B of communication between two specified nodes. We show that MFMI is polynomially solvable while MCFMI is NP -hard even for a bounded number of different interfaces and bounded degree networks. Moreover, we provide polynomial approximation algorithms for MCFMI and exact algorithms for relevant sub-problems. Finally, we experimentally analyze the proposed approximation algorithm, showing that in practical cases it guarantees a low approximation ratio.

I. INTRODUCTION

The interest in heterogeneous networks has rapidly grown during the last decades. Their success is certainly due to the wide range of applications for which such networks are designed. One of the most relevant property is the variety of the devices which might interact in order to exchange data. Heterogeneous networks are, in fact, composed of devices with different characteristics like computational power, energy consumption, communication interfaces, communication protocols, and so forth. In this paper, we are mainly interested in devices equipped with multiple interfaces (like Ethernet, ADSL, Bluetooth, WiFi, GPRS, etc.). A connection between two or more devices might be accomplished by means of different communication networks according to connectivity and quality of service requirements. The selection of the most suitable interface for a specific connection might depend on various factors. Such factors include: the availability of an interface in specific devices, the required communication bandwidth, the cost (in terms of energy consumption) of maintaining an active interface, the available neighbors, and so forth. While managing such connections, a lot of effort must be devoted to energy consumption issues. Devices are, in fact, usually battery powered and the network survivability might depend on their persistence in the network.

We study communication problems in heterogeneous networks supporting multiple interfaces. In the considered model, a network is described by a graph G = (V, E), where V represents the set of devices and E is the set of possible connections defined according to the distance between devices and the available interfaces that they share. Each e ∈ E is associated with a set of interfaces X(e) that are assigned to both its endpoints. The set of all the possible available interfaces in the network is then determined by e∈E X(e); we denote the cardinality of this set by k. We say that a connection is established when the endpoints of the corresponding edge share at least one active interface. If an interface x is activated at both the endpoints of some edge e = {u, v}, then nodes u and v consume some energy c(x) for maintaining x as active, and they provide a maximum communication bandwidth b(x) with all their neighbors which share interface x. It follows that a device holding interface x has both the incoming and the outgoing bandwidths bounded by b(i). In the paper, we assume that the connections are point-to-point. In this setting, we study two optimization problems whose aim is to guarantee a connection between two selected nodes s, t ∈ V , taking into account bandwidth constraints. First, we study the problem of finding the maximal possible bandwidth between two selected nodes s, t ∈ V . In detail, we consider all the interfaces of the network as active, so that all the connections in E are established. Then, we look for a suitable flow function that guarantees the maximum communication bandwidth between s and t. Successively, we study the problem of establishing a communication sub-network between two selected nodes s, t ∈ V of minimum cost in terms of energy consumption, while guaranteeing a minimum communication bandwidth B. In other words, we look for the minimum cost set of active interfaces among the network so that s is guaranteed to transfer data to t with a bandwidth of at least B. In general, the solution is not a path between s and t, but a more complex graph consisting of nodes with active interfaces might be required according to the topology and the available interfaces.

A. Related work

Multi-interface networks have recently been studied in a variety of contexts, usually focusing on the benefits of multiple interfaces available at each node. Many basic problems of standard network optimization can be reconsidered in such a setting [START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF], in particular, focusing on issues related to routing [START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF] and network connectivity [START_REF] Dangelo | Minimize the maximum duty in multi-interface networks[END_REF], [START_REF] Cavalcanti | Connectivity in multiradio, multi-channel heterogeneous ad hoc networks[END_REF], [START_REF] Faragó | The effect of multi-radio nodes on network connectivity-a graph theoretic analysis[END_REF]. The study of combinatorial problems on multi-interface networks has originated from [START_REF] Caporuscio | Energetic Performance of Service-oriented Multi-radio Networks: Issues and Perspectives[END_REF]. That paper, as well as [START_REF] Dangelo | Minimize the maximum duty in multi-interface networks[END_REF], [START_REF] Klasing | Cost Minimization in Wireless Networks with a Bounded and Unbounded Number of Interfaces[END_REF], investigates the Coverage problem, where the goal is the activation of the minimum cost set of interfaces in such a way that all the edges of G are established. Connectivity issues have been addressed in [START_REF] Dangelo | Minimize the maximum duty in multi-interface networks[END_REF], [START_REF] Athanassopoulos | Energy-efficient communication in multi-interface wireless networks[END_REF], [START_REF] Kosowski | Exploiting Multi-Interface Networks: Connectivity and Cheapest Paths[END_REF]. The goal becomes to activate the minimum cost set of interfaces in G in order to guarantee a path of communication between every pair of nodes. In [START_REF] Kosowski | Exploiting Multi-Interface Networks: Connectivity and Cheapest Paths[END_REF], the attention has been devoted to the Cheapest path problem. This corresponds to the well-known shortest path problem, but in the context of multi-interface networks.

A natural continuation on investigating such kind of networks is certainly to consider also quality of service constraints. Studies on the maximization of some network utility function (e.g., the throughput) while taking care of possible interferences between different wireless communications in multi-channel multi-radio wireless networks can be found in [START_REF] Bhandari | Scheduling in Multi-Channel Wireless Networks[END_REF], [START_REF] Lin | Distributed and provably efficient algorithms for joint channel-assignment, scheduling, and routing in multichannel ad hoc wireless networks[END_REF], [START_REF] Wan | Multiflows in multi-channel multi-radio multihop wireless networks[END_REF]. To the best of our knowledge, pure bandwidth issues have been never treated before in this context in terms of simple flow problems.

B. Our results

In this paper, we are interested in two fundamental optimization problems which take into account bandwidth constraints in the input network.

The first problem, called Maximum Flow in Multi-Interface Networks (MFMI), aims to find the maximal communication bandwidth that can be guaranteed between two given nodes. Such problem is similar to the classical problem of finding the maximum flow between two nodes in a network. The main difference resides in the fact that, in MFMI, the bandwidth capacities are associated to the interfaces instead of edges. Therefore, a node v can communicate with many other nodes by means of a single interface i but, if v uses the whole bandwidth of i to transmit to (receive from, resp.) a neighbor u, it cannot use i to transmit to (receive from, resp.) another neighbor w, even if i belongs to both v and w. Therefore, we assume that the communications are point-to-point. We show that this problem is optimally solvable in polynomial time, and we provide an algorithm to solve it.

The second problem aims to establish the cheapest way of communication between two given nodes while guaranteeing a minimum bandwidth of communication. Such problem, called Minimum-Cost Flow in Multi-Interface Networks (MCFMI) is similar to the better known Minimum Edge-Cost Flow [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF]. Again, we do not consider costs and capacities for the edges of the network but we have to cope with interfaces at the nodes that require some costs and can manage some maximum bandwidths. In the special case where there exists a oneto-one mapping between interfaces and connections, that is, each connection can be established by means of one interface different from any other, the two problems MCFMI and Minimum Edge-Cost Flow coincide. Hence, it is not surprising that MCFMI turns out to be NP -hard when the number k of interfaces is unbounded. However, in practical cases it is more realistic to consider a bounded number of interfaces. Despite the expectations, we show that the problem is NPhard even when k is a fixed small number. In detail, we prove that the problem is NP -hard for any fixed k ≥ 2 and ∆ ≥ 3, where ∆ is the maximum degree of the network, while it is

Unbounded NP-hard; (2 + ǫ)-apx in O(|V | k 2 ǫ ) for paths Fixed ∆ ≥ 3 Fixed k ≥ 2 NP-hard (from X3C) Fixed k ≥ 3
Not apx within Ω(log B), or within Ω(log log |V |)

Any k = 1 Opt. solvable in O(|V | + |E|) (equiv. shortest path)
Any bmax M -apx (optimal for constant bandwidth)

polynomially solvable when k = 1, or ∆ ≤ 2 and k = O(1). Moreover, we show that the problem is not approximable within Ω(log B) or Ω(log log |V |) for any fixed k ≥ 3, ∆ ≥ 3, unless P = NP . We then provide an approximation algorithm with ratio guarantee of bmax M , where b max is the maximum communication bandwidth allowed among all the available interfaces and M is the greatest common divisor among the bandwidths allowed by the interfaces and B. Hence, when the bandwidth is constant for all the interfaces, the optimal solution is provided. We also focus on particular cases by providing complexity results and polynomial algorithms for ∆ ≤ 2. Surprisingly, when k is unbounded and the network reduces to a single edge the problem remains NP -hard. Table I summarizes the results. Finally, we experimentally analyzed the bmax M -approximation algorithm, showing that, in practical cases, it guarantees a low approximation ratio which allows us to use it in real-world networks.

Outline: In the next section, we give the statements of the problems and introduce some useful notation. In Section III we give some preliminary results that will be used in the subsequent Sections IV and V. In Section IV, we study the computational complexity of the two problems by identifying the cases where they are NP -hard or solvable in polynomial time. In Section V, we study the approximation properties of the two problems by giving inapproximability lower bounds and approximation algorithms. In Section VI, we give an experimental study on one of the approximation algorithms proposed in Section V. Finally, in Section VII, we provide some concluding remarks.

II. DEFINITIONS AND NOTATION

Given a network, we denote by V the set of nodes. For each pair of nodes in V , the sharing function X : V × V → 2 {1,2,...,k} denotes the set of interfaces that the two nodes can use to communicate. Function X must satisfy the following properties: for each u in V , X(u, u) = ∅; for each u,v in V , X(u, v) = X(v, u). Function X induces a global assignment of the interfaces to the nodes in V given in terms of an appropriate interface assignment function W : V → 2 {1,2,...,k} defined as W (v) = u∈V X(u, v). If an interface i is in X(u, v) for some nodes u and v, then i ∈ W (u), i ∈ W (v), and u and v are close enough to communicate via interface i. It follows that, for each u, v in V , X(u, v) ⊆ W (u)∩W (v). The use of those functions represents a generalization of the model w.r.t. earlier works on the subject, including [START_REF] Angelo | Bandwidth Constrained Multi-Interface Networks[END_REF], [START_REF]Maximum Flow and Minimum-Cost Flow in Multi-Interface Networks[END_REF]. Note that, the above definitions of V , X induce a graph G = (V, E) where {u, v} ∈ E if and only if X(u, v) = ∅. We say that G is induced by the sharing function X. Unless otherwise stated, the graph G representing the network is assumed to be undirected and connected. In the remainder, we denote by ∆ the maximum node degree in G. The cost of activating an interface i is given by the cost function c : {1, 2, . . . , k} → Z + 0 and it is denoted as c(i). The bandwidth allowed by a given interface i is defined by the bandwidth function b : {1, 2, . . . , k} → Z + 0 and it is denoted as b(i). It follows that each node holding an interface i pays the same cost c(i) and provides the same bandwidth b(i) by activating i. However, MFMI does not require to minimize the cost of activating interfaces and therefore in this case we assume that all the interfaces are activated.

Problems MFMI and MCFMI are formulated as follows.

MFMI: Maximum Flow in Multi-Interface Networks

In: A set of nodes V , a source node s ∈ V , a target node t ∈ V , a set of interfaces I = {1, 2, . . . , k}, a sharing function X : V × V → 2 I , and an interface bandwidth function b :

I → Z + 0 . Sol: A flow function f : V × V × I → Z + 0 such that: 1) f (u, v, i) = -f (v, u, i) ∀ u, v ∈ V , i ∈ I; 2) f (u, v, i) = 0 if X(u, v) = ∅ ∀ u, v ∈ V , i ∈ I; 3) v∈V :f (u,v,i)>0 f (u, v, i) ≤ b(i) ∀u ∈ V , i ∈ I; v∈V :f (v,u,i)>0 f (v, u, i) ≤ b(i) ∀u ∈ V , i ∈ I; 4)
v∈V,i∈I f (u, v, i) = 0 ∀u ∈ V \ {s, t}; Aim: Maximize the total flow from s to t, F = v∈V,i∈I f (s, v, i) = v∈V,i∈I f (v, t, i).

MCFMI: Minimum-Cost Flow in Multi-Interface Networks

In: A set of nodes V , a source node s ∈ V , a target node t ∈ V , a set of interfaces I = {1, 2, . . . , k}, a sharing function X : V × V → 2 I , an interface cost function c : I → Z + 0 , an interface bandwidth function b : I → Z + 0 and a bound B ∈ Z + 0 .

Sol: An allocation of active interfaces W

A : V → 2 I , W A (v) ⊆ u∈V X(u, v), ∀ v ∈ V , and a flow function f : V × V × I → Z + 0 such that: 1) f (u, v, i) = -f (v, u, i) ∀ u, v ∈ V , i ∈ I; 2) f (u, v, i) = 0 if W A (u) ∩ W A (v) ∩ X(u, v) = ∅ ∀ u, v ∈ V , i ∈ I; 3) v∈V :f (u,v,i)>0 f (u, v, i) ≤ b(i) ∀u ∈ V , i ∈ I; v∈V :f (v,u,i)>0 f (v, u, i) ≤ b(i) ∀u ∈ V , i ∈ I; 4) v∈V,i∈I f (u, v, i) = 0 ∀u ∈ V \ {s, t}; 5) v∈V,i∈I f (s, v, i) = v∈V,i∈I f (v, t, i) ≥ B. Aim: Minimize the total cost of the active interfaces, c(W A ) = v∈V i∈WA(v) c(i).
For both problems MFMI and MCFMI, we denote by G = (V, E) the graph induced by the sharing function X, also

′ . W (s) = {1, 2}, W (v) = 1, 2, 3, W (t) = X(v, t) = {2, 3}, and X(s, v) = {1}. v s t {2, 3} {1, 2} {1, 2, 3} {1} {2, 3} t (s, 1) (t, 3) (t, 3) (s, 1) (t, 2) (t, 2) (v, 3) (v, 3) (v, 2) (v, 2) (s, 2) (s, 2) s (v, 1) (v, 1)
referred as the input graph. Graph G can be easily computed from X in time O(|V | + |E|). Note that we can consider two variants of the MCFMI problem: the parameter k can be considered as part of the input (this is called the unbounded case), or k may be a fixed constant (the bounded case). In both cases we assume k ≥ 2, since the case k = 1 admits an obvious solution given by a shortest path connecting s to t of maximum bandwidth b(1). The case where the cost function is constant for each interface is called the unit cost case.

III. PRELIMINARY RESULTS

The algorithms given in this paper for the general cases of MFMI and MCFMI are both based on a transformation of the graph G = (V, E) into a directed graph G ′ = (V ′ , A). G ′ is defined so that bandwidths and costs are associated to arcs rather than to interfaces. Informally, for each interface of each node, there is an arc which has the same cost and bandwidth of the considered interface. The head of each of such arcs is connected to the tail of another arc of the same kind if they share an interface or they represent different interfaces of the same node. As each of these arcs is associated with the cost and the bandwidth of the interface it represents, the activation of an interface is modeled with the usage of one of these arcs, preserving the bandwidth constraints and the activation costs. Moreover, although the arcs are directed, the possibility to communicate towards and from every node of the original graph is preserved (see also Fig. 1).

Formally, for each node v ∈ V and each interface i ∈ W (v), there are two nodes in V ′ denoted as (v, i) and (v, i):

V ′ = {(v, i), (v, i) | v ∈ V, i ∈ W (v)} ∪ {s, t}.
The arcs are the following:

A = {((v, i), (v, i)) | v ∈ V, i ∈ W (v)} ∪ {((v, i), (v, j)) | v ∈ V, i, j ∈ W (v) s.t. i = j} ∪ {((u, i), (v, i))| i ∈ X(u, v)} ∪ (s, (s, i)), ((t, j), t) | i ∈ W (s), j ∈ W (t) .
The capacity of each arc ((v, i), (v, i)) is set to b ′ ((v, i), (v, i)) = b(i) whereas the capacity of each other arc in A is unlimited and it is 0 for each pair in V × V \ A. The cost c ′ (a) of each arc a = ((v, i), (v, i)) is set to c(i) and it is 0 for the remaining arcs.

Given a flow function f ′ from s to t for G ′ , we define a flow function f from s to t in G as follows:

f (u, v, i)= f ′ ((u, i), (v, i)) -f ′ ((v, i), (u, i)) if i ∈ X(u, v) 0, otherwise.
The allocation of active interfaces at node u for MCFMI is defined as

W A (u) = {i ∈ W (u) | ∃v ∈ V s.t. f (u, v, i) = 0}.
In order to address concurrently MCFMI and MFMI, we define W A for MFMI as equivalent to the assignment function W induced by the sharing function X. Note that both functions f and W A can be computed in polynomial time once function f ′ is known.

The next lemma shows that, if we apply the above transformation to an instance I of MFMI or MCFMI and we compute a flow function f and an assignment of interfaces W A for I by using the above definition on some flow function f ′ of G ′ , then f satisfies Properties 1-4 needed by both the definitions of MFMI and MCFMI.

Lemma 3.1: Let f and W A be a flow function and an assignment of interfaces defined as above, then 1)

f (u, v, i) = -f (v, u, i) ∀ u, v ∈ V and i ∈ I; 2) f (u, v, i) = 0 if W A (u) ∩ W A (v) ∩ X(u, v) = ∅ ∀ u, v ∈ V and i ∈ I; 3) v∈V :f (u,v,i)>0 f (u, v, i) ≤ b(i) ∀ u ∈ V and i ∈ I; v∈V :f (v,u,i)>0 f (v, u, i) ≤ b(i) ∀ u ∈ V and i ∈ I; 4) v∈V,i∈I f (u, v, i) = 0 ∀ u ∈ V \ {s, t}. Proof:
We recall that, by definition of a flow function for a directed flow network:

0 ≤ f ′ (x, y) ≤ b ′ (x, y), for each (x, y) ∈ A (a) f ′ (x, y) = -f ′ (y, x), for each x, y ∈ V ′ (b) x∈V ′ f ′ (x, y) = 0, for each y ∈ V ′ \ {s, t}. (c)
In the following we prove the four properties. 1) If i ∈ X(u, v), then f (u, v, i) = f (v, u, i) = 0. In fact, by definition of f and by Property (b)

f (u, v, i) = f ′ ((u, i), (v, i)) -f ′ ((v, i), (u, i)) = -(f ′ ((v, i), (u, i)) -f ′ ((u, i), (v, i))) = -f (v, u, i). 2) If W A (u) ∩ W A (v) ∩ X(u, v) = ∅, then for each i ∈ I either i ∈ W A (u) or i ∈ W A (v) or i ∈ X(u, v). If i ∈ W A (u), then by definition of W A (u) f (u, v, i) = 0. If i ∈ W A (v), then by definition of W A (v), f (v, u, i) = 0, moreover by the above property, f (u, v, i) = -f (v, u, i) = 0. If i ∈ X(u, v), then by definition of f , f (u, v, i) = 0.
3) We formally provide only the proof for the first inequality as the second one follows from similar arguments. By definition of f ,

v∈V :f (u,v,i)>0 f (u, v, i) = v∈V :f (u,v,i)>0 (f ′ ((u, i), (v, i)) -f ′ ((v, i), (u, i))) . By Property (a), for each v ∈ V , f ′ ((v, i), (u, i)) ≥ 0 and f ′ ((u, i), (v, i)) ≥ 0, then v∈V :f (u,v,i)>0 (f ′ ((u, i), (v, i)) -f ′ ((v, i), (u, i))) ≤ v∈V :f (u,v,i)>0 f ′ ((u, i), (v, i)).
By the definition of b ′ and Property (a),

v∈V :f (u,v,i)>0 f ′ ((u, i), (v, i)) ≤ v∈V f ′ ((u, i), (v, i)).
By Property (c), applied to (u, i),

v∈V f ′ ((u, i), (v, i)) = f ′ ((u, i), (u, i)) -j∈I\{i} f ′ ((u, i), (u, j)). Again by Prop- erty (a), f ′ ((u, i), (u, j)) ≥ 0, for each j ∈ I \ {i}, then f ′ ((u, i), (u, i)) - j∈I\{i} f ′ ((u, i), (u, j) ≤ f ′ ((u, i), (u, i)) ≤ b(i). The last inequality directly follows from Property (a). 4) By definition of f , f (u, v, i) = 0 if v = u or i ∈ X(u, v), hence v∈V,i∈I f (u, v, i) = v∈V \{u} i∈X(u,v) (f ′ ((u, i), (v, i)) -f ′ ((v, i), (u, i))). By Property (c), applied to nodes (u, i), v∈V \{u} i∈X(u,v) f ′ ((u, i), (v, i)) = v∈V \{u} i∈X(u,v) f ′ ((u, i), (u, i)) -j∈X(u,v) j =i f ′ ((u, i), (u, j)) .
Again, by Property (c), applied to nodes (u, i),

v∈V \{u} i∈X(u,v) f ′ ((v, i), (u, i)) = v∈V \{u} i∈X(u,v) f ′ ((u, i), (u, i)) -j∈X(u,v) j =i f ′ ((u, j), (u, i)) .
Hence,

v∈V \{u} i∈X(u,v) (f ′ ((u, i), (v, i)) -f ′ ((v, i), (u, i))) = v∈V \{u} i∈X(u,v) j∈X(u,v) j =i f ′ ((u, j), (u, i))- j∈X(u,v) j =i f ′ ((u, i), (u, j)) = 0,
in fact, for any pair of interfaces p and q such that p = q, we have that, when i = p and j = q, the related term of the above sum is f ′ ((u, q), (u, p))f ′ ((u, p), (u, q)), on the contrary, when i = q and j = p, it is f ′ ((u, p), (u, q))-f ′ ((u, q), (u, p)) and hence the overall sum is 0.

IV. COMPUTATIONAL COMPLEXITY

In this section we study the computational complexity of MFMI and MCFMI. We first prove that MFMI is optimally solvable in polynomial time in the general case, we then focus on MCFMI. We prove that MCFMI is NP -hard even in the restricted case of unit cost, fixed k ≥ 2, and fixed ∆ ≥ 3. Then we consider graphs of bounded degree ∆ ≤ 2. As announced in Table I, we prove that, when the number of interfaces k is fixed, the problem can be optimally solved in polynomial time. On the other hand, if k is unbounded, we show that the problem remains NP -hard. Moreover, when the bandwidth function b is a constant, then MCFMI is solvable in polynomial time (see Corollary 5.3 in the next section).

A. General Case

Let A be an algorithm that finds a maximum flow in a graph

H = (V H , E H ) in polynomial time P A (|V H | + |E H |). Theorem 4.1: MFMI is optimally solvable within O(|V |k 2 + |E| + P A (|V |k 2 + |E|)) time.
Proof: Given an instance I 1 of MFMI, the algorithm first transforms the graph G and the function b of I 1 into a graph G ′ and a function b ′ as described in Section III, obtaining an instance I 2 of the classical maximum flow problem. Then, in polynomial time, it finds a maximal flow function f ′ for I 2 by using a maximum flow algorithm. Finally, the algorithm obtains a maximal flow function f for I 1 from f ′ by using the transformation given in Section III. The computational time required by such an algorithm is given by the cost of transforming I 1 into I 2 and that of solving I 2 . As the graph defined for We now show that f is an optimal solution for I 1 . By Lemma 3.1, f satisfies properties 1-4 of the definition of MFMI. We show that f is maximal by contradiction. We recall that by definition of maximal flow function,

I 2 has O(|V |k) nodes and O(|V |k 2 + |E|) edges,
v∈V ′ f ′ (s, v) is maximal. By contradiction, let us suppose that there exists a flow function f ′′ : V × V × I → Z + 0 for I 1 such that v∈V,i∈I f ′′ (s, v, i) > v∈V,i∈I f (s, v, i). We define a flow function f ′′′ : V ′ × V ′ → Z + 0 for I 2 as follows, if i ∈ X(u, v), f ′′′ ((u, i), (v, i)) = f (u, v, i) if f (u, v, i) > 0 0 otherwise. For edges in {((v, i), (v, i)) | v ∈ V, i ∈ W (v)} ∪ {((v, i), (v, j)) | v ∈ V, i, j ∈ W (v) s.t. i = j},
f ′′′ is defined in order to satisfy the flow conservation constraints, and it is 0 for any other pair in V × V .

Similar arguments as Lemma 3.1 can be used to show that f ′′′ fulfills the properties of flow functions and that

v∈V ′ f ′′′ (s, v) = v∈V,i∈I f ′′ (s, v, i), v∈V ′ f ′ (s, v) = v∈V,i∈I f (s, v, i). It follows that v∈V ′ f ′′′ (s, v) = v∈V,i∈I f ′′ (s, v, i) > v∈V,i∈I f (s, v, i) = v∈V ′ f ′ (s, v), a contradiction to the maximality of f ′ .
Theorem 4.2: MCFMI is strongly NP -hard even when restricted to the unit cost interface case for any fixed ∆ ≥ 3 and k ≥ 2.

Proof: We prove that the underlying decisional problem, denoted by MCFMI D , is in general NP -complete. We need to add one further bound D ∈ Z + 0 such that the problem consists in deciding whether there exists an activation function which induces a total cost of the active interfaces of at most D.

Given an allocation function of active interfaces for an instance of MCFMI D , checking whether the induced subgraph allows a bandwidth greater than or equal to B of total cost smaller than or equal to D requires linear time in the number of edges of the input graph G. Then, MCFMI D is in NP . The proof proceeds by a polynomial reduction from the wellknown Exact Cover by 3-Sets problem. The problem is known to be NP -complete [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF] and it can be stated as follows:

T (3) T (3) T (3) s N (3) N (3) N (3) c 1 c 2 c |C| N (1) N (1) N (1) N (1)
T (3q + 1) t T (µ) T (µ) T (µ)
X3C: Exact Cover by 3-Sets

Input:

Set S with |S| = 3q and a collection C of 3element subsets of S. Question: Is there an exact set cover for S, i.e. a subset C ′ ⊆ C such that |C ′ | = q and every element of S belongs to exactly one member of C ′ ?

Given an instance of X3C, we construct an instance of MCFMI D where the graph G consists of copies of subgraphs N (ℓ) and T (ℓ), ℓ ≥ 1 (see Fig. 2). Subgraph N (ℓ) consists of 3ℓ nodes {x 1 , x 2 , . . . , x ℓ } ∪ {y 1 , y 2 , . . . , y ℓ } ∪ {w 1 , w 2 , . . . , w ℓ } and edges {x i , x i+1 }, {w i , w i+1 }, for i = 1, 2, . . . , ℓ -1 and {x i , y i }, {y i , w i }, for i = 1, 2, . . . , ℓ. Subgraph T (ℓ) is a binary tree consisting of a complete binary tree BT with 2 ⌈log 2 ℓ⌉ -1 nodes, and ℓ nodes adjacent to the leaves of BT . These nodes are the only leaves of T (ℓ), i.e. every leaf of BT is connected to at least one leaf of T (ℓ). We call r the root of T (ℓ). Note that, each path from r to a leaf of T (ℓ) is constituted of ⌈log 2 ℓ⌉ + 1 nodes. Moreover, when ℓ = 1, BT is empty and T (ℓ) consists of a single node.

For the sake of simplicity, in this proof we first define the graph G and then we define functions W and X accordingly. See Fig. 3 for a visualization of G. Let s and t be two nodes of G. For each element C i of C, i = 1, 2, . . . , |C|, G contains a node c i , a copy of N (3), denoted as N i (3) and a copy of T (3), denoted as T i (3), with root r i and leaves l i 1 , l i 2 , l i 3 . Nodes x i 1 and w i 3 of N i (3) are adjacent to c i and r i , respectively. All nodes c i form a path P in G, that is {c i , c i+1 } is an edge of G, for i = 1, 2, . . . , |C| -1. Node s of G is adjacent to c 1 , while node c |C| is adjacent to node x 0 1 belonging to a copy N 0 (1) of N (1) with nodes x 0 1 , y 0 1 and w 0 1 . Let e j , j = 1, 2, . . . , 3q, be the elements of S and let µ(e j ) be the number of sets C i ∈ C containing e j , for each j. Let µ = max j {µ(e j )}. For each element e j , G contains a copy of T (µ), called T j (µ), with root r j , and a copy N j (1) of N (1), with nodes x j 1 , y j 1 and w j 1 . Root r j is adjacent to x j 1 ∈ N j (1), for each j = 1, 2, . . . , 3q. If e j is in C i , for some i and j, then there is an edge from a leaf of T i (3) to a leaf of T j (µ).

These edges are pairwise disjoint. Note that, even if each leaf of T i (3), i = 1, 2, . . . , |C| is adjacent to a leaf in T j (µ), for some j ∈ {1, 2, . . . , 3q}, the contrary is not true: there could be a leaf of T j (µ), for some j, not adjacent to any leaf of

T i (3), i = 1, 2, . . . , |C|.
G also contains a copy of T (3q+1), having the root adjacent to node t, and leaves adjacent to nodes w j 1 , j = 0, 1, . . . , 3q. The set of interfaces

I is {1, 2}, with c(1) = c(2) = 1 and b(1) = 1, b(2) = 3q + 1.
Function W is defined as follows. All the nodes in G have interface 2 apart from nodes labeled y in the copies of N (1) and N (3). All the nodes in the copies of N (1) and N (3) have interface 1: no further node in G has interface 1. Function X is defined as follows, given two nodes u, v in G,

X(u, v) = W (u) ∩ W (v) if {u, v} ∈ E ∅ otherwise.
When all the interfaces of the nodes in copies of N (ℓ) (T (ℓ), resp.), for a certain ℓ ≥ 0, are active the total cost is 5ℓ (2 ⌈log 2 ℓ⌉ -1 + ℓ, resp.). In T (ℓ), when only the interfaces of the nodes in a single path from r to a leaf are active, the total cost is ⌈log 2 ℓ⌉ + 1. Let B = 3q + 1 and

D = |C| + q(42 + 3⌈log 2 µ⌉) + 2 ⌈log 2 (3q+1)⌉ + 7.
Assume that X3C has a positive answer, i.e., there exists an exact set cover C ′ = {C i1 , C i2 , . . . , C iq } ⊆ C for S. We show that also MCFMI D has a positive answer, i.e., there exists an activation function W A of the available interfaces such that the bandwidth allowed from s to t is bigger than or equal to B and the total cost is smaller than or equal to D. Function W A is defined as follows. Along with interfaces of nodes s, t, all the interfaces of nodes in T (3q + 1), N j (1), j = 0, 1, . . . , 3q, and c i , i = 1, 2, . . . , |C|, are active. All the interfaces of nodes in N ij (3) and T ij (3), for each C ij ∈ C ′ , j = 1, 2, . . . , q, are active. Moreover, if e i ∈ S is covered by C j ∈ C ′ , then all the interfaces of nodes in T j (µ) belonging to the path from r j to a leaf in T i (3) are active. No further interface is active. The flow function is defined as 1 in nodes y of active copies of N (1) and N (3) and in the remainder of G it is defined to satisfy the flow conservation constraints.

The total cost of active interfaces is given by 2, for nodes s and t; |C|, for nodes c i ∈ P , i = 1, 2, . . . , |C|; 15q + 6q for nodes in N ij (3) and T ij (3), j = 1, 2, . . . , q; 3q(⌈log 2 µ⌉ + 1) for nodes in T j (µ), j = 1, 2, . . . 3q; 5(3q + 1) for nodes in N j (1), j = 0, 1, . . . 3q; and 2 ⌈log 2 (3q+1)⌉ + 3q for nodes in T (3q + 1). Summing up all the values we obtain a cost equal to D.

Regarding the total bandwidth, note that a copy of N (ℓ) has a maximum bandwidth of ℓ. As X3C has a positive answer, each element of S is covered, then the flow through each subgraph N j (1), j = 1, 2, . . . , 3q, is exactly 3q. As all the interfaces in P are active, we also have a flow of 3q + 1 through N 0 (1) that reaches t through the T (3q + 1) subgraph. Then MCFMI D has a positive answer. Now, let us assume we have a positive answer to MCFMI D . As the total flow received by t is greater than or equal to B = 3q +1, there is a flow of value 1 in each subgraph N j (1), j = 0, 1, . . . , 3q, meaning that each element of S is covered. Let us suppose, by contradiction, that the flow reaching the N j (1), j = 1, 2, . . . , 3q subgraphs, implies the activation of the interfaces in q ′ > q subgraphs among the N i (3), i = 1, 2, . . . , |C| copies of N (3). In this case there will be q ′ 1 subgraphs having one unit of flow, q ′ 2 subgraphs having 2 units of flow, and q ′ 3 subgraphs having 3 units of flow such that q ′ 1 + 2q ′ 2 + 3q ′ 3 = 3q. The total cost for the interfaces activation is: 2, for nodes s and t; |C|, for nodes in P (all the interfaces in P are active as N 0 (1) receives one unit of flow); 7q ′ 1 +11q ′ 2 +15q ′ 3 for nodes in N i (3); 6q for nodes in T i (3), i = 1, 2, . . . , q; 3q(⌈log 2 µ⌉+1) for nodes in T j (µ), j = 1, 2, . . . 3q; 5(3q + 1) for nodes in N j (1), j = 0, 1, . . . 3q, and 2 ⌈log 2 (3q+1)⌉ + 3q for nodes in T (3q + 1).

Then the total cost is

|C| + q(27q + 3⌈log 2 µ⌉) + 2 ⌈log 2 (3q+1)⌉ + 7 + 7q ′ 1 + 11q ′ 2 + 15q ′ 3 . As 7q ′ 1 + 11q ′ 2 + 15q ′ 3 > 5(q ′ 1 + 2q ′ 2 + 3q ′ 3 ) = 15q
, the total cost is greater than D, a contradiction. Hence there are exactly q subgraphs N ij (3), j = 1, 2, . . . , q with 3 units of flow each and the corresponding sets C ij , j = 1, 2, . . . , q, represent a solution for X3C.

B. Particular cases for MCFMI, ∆ ≤ 2

Theorem 4.2 shows that MCFMI is NP -hard even for fixed ∆ ≥ 3 and k ≥ 2. As the case where k = 1 is trivial, we now focus on the case that ∆ ≤ 2. For ∆ ≤ 1, the input graph can be composed of either one single node or two nodes connected by one edge. In the first case, there are no interfaces to be activated, as the source and the destination coincide. In the second case, the problem already starts to be interesting.

Theorem 4.3: MCFMI is polynomially solvable within O(1) time in the bounded case with ∆ = 1.

Proof: MCFMI can be solved by an exhaustive search among all the possible combinations of interfaces shared by s and t. The number of such combinations is O(2 k ). Among them, a resolution algorithm has to choose the cheapest one that guarantees at least B bandwidth.

For the unbounded case, i.e., when k is not a given constant, the same arguments of Theorem 4.3 do not apply to MCFMI as the provided algorithm would show an exponential behavior. Surprisingly, in this setting the problem turns out to be already NP -hard by means of a simple polynomial transformation from the well known Minimization Knapsack problem [START_REF] Görtz | Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem[END_REF], [START_REF] Güntzer | Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem[END_REF].

M inKP : Minimization Knapsack When ∆ = 1, that is when the input graph G consists of a single edge from s to t, the required solution must select a subset of interfaces among the ones shared by s and t in such a way that a bandwidth of B is guaranteed, and the cost for activating such interfaces is minimized. Intuitively, this particular case of MCFMI is equivalent to the M inKP problem.

Theorem 4.4: MCFMI is polynomially equivalent to M inKP in the unbounded case with ∆ = 1.

Proof: We have to show that there exist two polynomial time algorithms A and B such that, for each instance I 1 of M inKP , A(I 1 ) returns an instance I 2 of MCFMI, for any solution σ ′ of I 2 , B(σ ′ ) = σ is a solution for I 1 , and the values of solutions σ and σ ′ are equal. Moreover, we have to show that there exist two polynomial time algorithms A -1 and B -1 such that, for each instance I 2 of MCFMI, A -1 (I 2 ) returns an instance I 1 of M inKP , for any solution σ of I 1 , B -1 (σ) = σ ′ is a solution for I 2 , and the values of solutions σ and σ ′ are equal.

We now show the first part of the above statement by defining the polynomial algorithms A and B. Given an instance I 1 of M inKP , we consider an instance I 2 of MCFMI made of nodes s and t, and, for each item i of I 1 , an interface i shared between s and t with cost c(i) = 1 2 p i and bandwidth b(i) = w i . Hence W (s) = W (t), moreover, function X is defined as X(s, t) = W (s). Finally, let k = n and B = d. Note that, if, for some i, p i is an odd number, we can multiply all the profits p i of a factor 2 in order to have c(i) ∈ Z + 0 for each i = 1, 2, . . . , n. This does not affect the generality of the proof as it is enough to divide by 2 the value of the objective function for the solution of I 1 which will be defined in the following. A feasible solution for I 2 selects a set of interfaces W , by means of an activation function, in such a way that B ≤ i∈W b(i). As d = B ≤ i∈W b(i) = i∈W w i and the cost of activating interfaces in W at both s and t is 2 i∈W c(i) = i∈W p i , we can define algorithm B as the algorithm which selects items W in order to output a solution for I 1 . Finally, both A and B are polynomial time algorithms. This proves the first part of the theorem. For the second part of the theorem, it is enough to note that algorithms A and B can be naturally inverted.

Corollary 4.5: MCFMI is NP -hard in the unbounded case with ∆ = 1 and it admits a pseudo-polynomial-time algorithm.

For ∆ = 2, the input graph of MCFMI is either a path or a cycle. Clearly, from Corollary 4.5, MCFMI remains NPhard in the unbounded case. The following theorem gives a polynomial time algorithm for the bounded case. In the next section, we will derive a pseudo-polynomial-time algorithm for the unbounded case.

In the remainder, for a set of interfaces W , we denote as c(W ) the cost of activating the interfaces in W , formally: c(W ) = i∈W c(i).

Theorem 4.6: MCFMI is solvable within O(|V |) time in the bounded case when the input graph is a path.

Proof: Let us denote the input path as a sequence of n nodes: s ≡ x 0 , x 1 , . . . , x n-1 ≡ t. Given a node x ℓ , 1 ≤ ℓ ≤ n -1, γ(x ℓ ) denotes the set of sub-sets of interfaces of x ℓ , shared with x ℓ-1 , whose total band-width is greater than or equal to B, formally: γ(x ℓ ) = W ⊆ X(x ℓ , x ℓ-1 ) i∈W b(i) ≥ B . Then, the minimum cost is given by:

OPT = min {2c(W 1 ) + c(W 2 \ W 1 ) + c(W 2 ) + . . . . . . + c(W n-1 \ W n-2 ) + c(W n-1 ) | W 1 ∈ γ(x 1 ), W 2 ∈ γ(x 2 ), . . . , W n-1 ∈ γ(x n-1 )} ,
where 2c(W 1 ) is the cost of interfaces used to connect x 0 to x 1 and c(W ℓ \ W ℓ-1 ) + c(W ℓ ) is the cost of interfaces used to connect x ℓ-1 to x ℓ , 2 ≤ ℓ ≤ n -1. In particular, c(W ℓ \W ℓ-1 ) is the cost of activating in x ℓ-1 the interfaces in W ℓ not contained in W ℓ-1 and c(W ℓ ) is the cost of activating interfaces W ℓ in x ℓ .

For each 1 ≤ ℓ ≤ n -1, let us define the function C ℓ : γ(x ℓ ) → Z + 0 as the minimum cost needed to establish a communication path from s to node x ℓ with bandwidth guarantee greater than or equal to B by activating interfaces W ∈ γ(x ℓ ) in x ℓ , formally:

C ℓ (W ) = min {2c(W 1 ) + c(W 2 \ W 1 ) + c(W 2 ) + . . . . . . + c(W \ W ℓ-1 ) + c(W ) | W 1 ∈ γ(x 1 ), W 2 ∈ γ(x 2 ), . . . , W ℓ-1 ∈ γ(x ℓ-1 )} .
By definition, OPT = min W ∈γ(xn-1) C n-1 (W ). Hence it is enough to show that functions C ℓ , for each 1 ≤ ℓ ≤ n -1, can be computed in O(n) time. By cut-and-paste arguments, it follows that:

C ℓ (W ) = min W ℓ-1 ∈γ(x ℓ-1 ) {C ℓ-1 (W ℓ-1 ) +c(W \ W ℓ-1 ) + c(W )} .
Therefore, functions C ℓ , can be computed by using dynamic programming starting from C 1 (W ) = 2c(W ), for each W ∈ γ(x 1 ). Moreover, as k is a bounded constant, |γ(x ℓ )| ≤ 2 k = O(1). Hence, given 1 ≤ ℓ ≤ n -1 and W ∈ γ(x ℓ ), computing C ℓ (W ) requires O(1) time and computing function C ℓ requires O(1) time. Then, all the functions C ℓ , for all

1 ≤ ℓ ≤ n -1, can be computed in O(n) time.
When the input graph is a cycle, since there are two paths from s to t, it is not always clear how the bandwidth B must be split among the two possible ways. However, the following theorem can be stated for the bounded case.

Theorem 4.7: MCFMI is solvable within O(|V |) time in the bounded case when the input graph is a cycle.

Proof: Let P 1 and P 2 be the two edge-disjoint paths from s to t composing the input cycle. As by definition, b(i) ∈ Z + 0 , 1 ≤ i ≤ k, the required flow B is provided by summing two integers β 1 and β 2 that are the contributions to the total flow passing via P 1 and P 2 , respectively. The values β 1 and β 2 vary among all the integers obtainable by summing the bandwidths provided by each possible subset of interfaces, i.e., β 1 and β 2 can assume at most 2 k values. For each subset of interfaces of s and for each subset of interfaces of t, the algorithm proposed by Theorem 4.6 is applied to solve the MCFMI instance arising for P 1 with bound β 1 , and the one arising for P 2 with bound β 2 = B -β 1 . The over all trials are at most 2 2k , each of them requires 2 k tests, one for each possible value of β 1 . As k = O(1), then 2 3k = O(1). Among the obtained solutions, we choose the cheapest one which guarantees a flow of at least B from s to t. Such algorithm requires to run O(1) times the algorithm in Theorem 4.6 and hence it requires O(|V |) overall computational time.

V. APPROXIMATION

In this section, we study the approximation properties of MCFMI. We first show that, unless P = NP , MCFMI cannot be approximated within a factor of Ω(log B), or within a factor of Ω(log log |V |), even for fixed ∆ ≥ 3 and fixed k ≥ 3. We also provide a bmax M -approximation algorithm for the general case, where b max = max i∈I b(i) and M is the greatest common divisor among the bandwidths allowed by the interfaces and the required bandwidth B. Finally, we analyze the case of fixed ∆ ≤ 2. As in the previous section, it has been shown that, in this case, MCFMI is polynomially solvable if k is fixed, then we focus on the approximability of the unbounded case. We give two results which show that, if ∆ = 1 or the input graph is a path, then MCFMI admits a FPTAS, while in the case that the input graph is a cycle the approximability of MCFMI remains open.

A. General case

Theorem 5.1: MCFMI cannot be approximated within a factor of Ω(log B), or within a factor of Ω(log log |V |), for any fixed ∆ ≥ 3 and k ≥ 3, unless P = NP .

Proof: We will show the statement by providing an approximation gap preserving reduction [START_REF] Vazirani | Approximation Algorithms[END_REF] from the Set Cover (SC) problem to MCFMI.

SC: Set Cover

In: A set U with n elements and a collection S = {S 1 , S 2 , . . . , S q } of subsets of U . Sol: A cover for U , i.e. a subset S ′ ⊆ S such that every element of U belongs to at least one member of S ′ . Aim: Minimize |S ′ |.

We first show that there exists a polynomial time algorithm that transforms any instance I 1 of SC into an instance I 2 of MCFMI such that the optimum value SOL * SC on I 1 for the problem SC is greater than or equal to the optimum value SOL * MCFMI on I 2 for the problem MCFMI. The transformation is similar to the one provided for Theorem 4.2 (see Fig. 4). The graph G is given by two nodes s and t where s is adjacent to the root node of a copy of T (|S|) and t to the root node of a copy of T (n). For each element S i of S, i = 1, 2, . . . , |S|, G contains a copy of N (1), denoted by N i (1) and a subgraph T (|S i |) with root r i adjacent to node

w i 1 ∈ N i (1). Each node x i 1 ∈ N i (1)
is adjacent to a different leaf of T (|S|). Let u j , j = 1, 2, . . . , |U |, be the elements of U and let µ j be the number of sets S i ∈ S containing u j , for each j. For each element u j , G contains a subgraph T (µ j ), with root r j , and a copy N j (1) of N (1), with nodes x j 1 , y j 1 and w j 1 . Root r j is adjacent to x j 1 ∈ N j (1), and each node x j 1 ∈ N j (1) is adjacent to a different leaf of T (n), for each j = 1, 2, . . . , n. If u j ∈ S i , for some i and j, then there is an

N (1)

N ( 1)

N (1) t T (n) T (µ n ) T (µ 2 ) T (µ 1 ) s T (|S|) N (1) N (1) N (1) T (|S 2 |) T (|S q |) T (|S 1 |)
edge from a leaf of T (|S i |) to a leaf of T (µ j ). These edges are pairwise disjoint.

The set of interfaces is {1, 2, 3}, with c(1) = 0, c( 2

X(u, v) = W (u) ∩ W (v) if {u, v} ∈ E ∅ otherwise.
Let B = n, we denote by SOL SC (I 1 , σ 1 ) the value of the cost function of SC for a solution σ 1 on instance I 1 , and let SOL * SC (I 1 ) be the optimal cost for SC on instance I 1 . Moreover, let us denote by SOL MCFMI (I 2 , σ 2 ) the cost function of MCFMI of a solution σ 2 on instance I 2 , and let SOL * MCFMI (I 2 ) be the optimal cost for MCFMI on instance

I 2 .
Let us assume that we have an optimal solution {S i 1 , S i 2 , . . . , S i m } for SC. Then, by activating all the interfaces 1 and 3 in G and the interfaces 2 only in the nodes of subgraphs N i j (1), j = 1, 2, . . . , |S|, we obtain a feasible solution σ for I 2 such that SOL(I 2 , σ) ≤ 3SOL * SC (I 1 ), hence: SOL * MCFMI (I 2 ) ≤ 3SOL * SC (I 1 ). Now we show that it is possible to transform in polynomial time any solution σ 2 for the instance I 2 of MCFMI into a solution σ 1 for the instance I 1 of SC such that 3SOL SC (I 1 , σ 1 ) = SOL MCFMI (I 2 , σ 2 ). A solution σ 2 consists of a flow of n units passing through each subgraph N j (1), j = 1, 2, . . . , n, corresponding to a covering of all the elements in U . A solution σ 1 then consists of the sets S i 1 , S i 2 , . . . , S i m corresponding to those subgraphs N i j (1), j = 1, 2, . . . , m, having a positive flow. As consequence, 3SOL SC (I 1 , σ 1 ) = SOL MCFMI (I 2 , σ 2 ).

If there exists an α factor approximation algorithm A for MCFMI, we would obtain an α factor approxima-tion algorithm for SC. In fact, given an instance I 1 of SC, we could find a solution σ 1 for SC by using the above transformation from I 1 to an instance I 2 of MCFMI and applying A to find an α-approximate solution σ 2 . Hence obtaining SOL SC (I 1 , σ 1 ) = 1 3 SOL MCFMI (I 2 , σ 2 ) ≤ α 3 SOL * MCFMI (I 2 ) ≤ αSOL * SC (I 1 ). In [START_REF] Alon | Algorithmic construction of sets for k-restrictions[END_REF], the authors show that no approximation algorithm for SC exists with an approximation factor less than Ω(log n). Then there is no algorithm for MCFMI with an approximation factor less than Ω(log B), since we set B = n. By observing that for the instance I 2 , |V | ≤ a 1 |S| + a 2 n + a 3 ≤ 2 n a 1 + a 2 n + a 3 ≤ 2 n a 4 for certain constants a 1 , a 2 , a 3 and a 4 = 3 max{a 1 , a 2 , a 3 }, we have n ≥ log(|V |/a 4 ). By using the same inapproximability result as before, we obtain the thesis.

Theorem 5.1 also holds when the number of interfaces is unbounded. We now provide a bmax M -approximation algorithm for any instance of MCFMI, where b max is the maximum bandwidth value among the interfaces in I and M is the greatest common divisor among the bandwidths allowed by the interfaces and the required bandwidth B. The algorithm consists in relaxing MCFMI to the well-known Integral Minimum Cost Flow (IMCF ) problem [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF]. In the proof of the next theorem, we transform an instance of MCFMI into an instance of IMCF , and we show that such a transformation guarantees an approximation factor of bmax M . Let A be an algorithm which optimally solves IMCF on a graph Proof: Given an instance I 1 of MCFMI, the algorithm works in four phases. First it transforms the graph G and functions b and c of I 1 into a graph G ′ and functions b ′ and c ′ as described in Section III. Hence, we obtain an instance I 2 of an equivalent problem defined on a directed graph G ′ = (V ′ , A) without using multiple interfaces but associating costs and bandwidths only to arcs in A. The aim of such problem is finding a flow function which satisfies flow constraints and such that the flow going from the source s to the sink t is greater than or equal to B. Then, the algorithm transforms I 2 into an instance I 3 of IMCF . In the third phase, the algorithm solves I 3 by using a known algorithm and, finally, it transforms the obtained solution for I 3 into a solution for I 2 made of a flow function f ′ . Function f ′ can be transformed into a solution for I 1 , as described in Section III, obtaining a flow function f and an assignment of interfaces W A .

H = (V ′ , E ′ ) in polynomial time P A (|V ′ | + |E ′ |).
In the following, we first show that the problems of solving I 1 and I 2 are equivalent, then we show how to approximate an optimal solution for I 2 by optimally solving I 3 .

Given a solution for I 2 , which defines a flow function f 2 , we can define a solution for I 1 by assigning a flow function f 1 as explained in Section III, that is,

f 1 (u, v, i)= f 2 ((u, i), (v, i)) -f 2 ((v, i), (u, i)) if i ∈ X(u, v) 0, otherwise.
Vice versa, given a solution for I 1 , which defines a flow function f ′ 1 , we can define a solution for I 2 by assigning a

flow function f ′ 2 as follows, if i ∈ X(u, v), f ′ 2 ((u, i), (v, i)) = f ′ 1 (u, v, i) if f ′ 1 (u, v, i) > 0 0 otherwise. In edges in {((v, i), (v, i)) | v ∈ V, i ∈ W (v)} ∪ {((v, i), (v, j)) | v ∈ V, i, j ∈ W (v) s.t. i = j}, f ′
2 is defined in order to satisfy flow conservation constraints, and it is 0 for any other pair in V × V . We now prove that the feasibility of f 2 (f ′ 1 , resp.) implies the feasibility of f 1 (f ′ 2 , resp.). By Lemma 3.1, properties 1-4 of the definition of MCFMI follows. Moreover, similar arguments can be used to show that f ′ 2 satisfies flow constraints and that

v∈V ′ f 2 (s, v) = v∈V,i∈I f 1 (s, v, i) v∈V,i∈I f ′ 1 (s, v, i) = v∈V ′ f ′ 2 (s, v).
Hence, to show property 5 of the definition of MCFMI, it is enough to note that if

v∈V ′ f 2 (s, v) ≥ B ( v∈V,i∈I f ′ 1 (s, v, i) ≥ B, resp.) then v∈V,i∈I f 1 (s, v, i) ≥ B ( v∈V ′ f ′ 2 (s, v) ≥ B, resp.
). This shows that the feasibility of f 2 (f ′ 1 , resp.) implies the feasibility of f 1 (f ′ 2 , resp.). To conclude the first part of the proof, note that, the cost of

f 2 (f ′ 1 , resp.) is equal to the cost of f 1 (f ′ 2 , resp.) as the cost of arcs ((v, i), (v, i)) in A is c(i)
and it is 0 for any other arc. By the above discussion it follows that we can solve I 1 by solving I 2 .

We find an approximate solution for I 2 by using an IMCF instance. The IMCF problem consists of finding an integral flow greater than or equal to a given quantity Θ between two nodes in a directed graph H where each arc a has a capacity β(a) and cost χ(a). The objective is to minimize the function a∈A + χ(a) • f ′′ (a), where f ′′ (a) is the flow on arc a and A + is the set of arcs with positive flow. This problem admits a polynomial time algorithm (see, e.g., [START_REF] Lawer | Combinatorial Optimization: Networks and Matroids[END_REF]).

We obtain an IMCF instance I Let us denote as f * and f IMCF two optimal flow functions for I 2 and I 3 , respectively and as A * and A IMCF the corresponding sets of arcs with positive flow. By definition,

OPT = a∈A * c ′ (a). As f * (a) ≤ b ′ (a), it follows that a∈A * c ′ (a) ≥ a∈A * c ′ (a) • f * (a) b ′ (a) = a∈A * χ(a) • f * (a).
By the optimality of A IMCF it follows that

a∈A * χ(a) • f * (a) ≥ M • a∈A IMCF χ(a) • f IMCF (a) = M • a∈A IMCF c ′ (a) b ′ (a) • f IMCF (a). As f IMCF (a) ∈ Z + 0 , for each a ∈ A, then f IMCF (a) ≥ 1, for each a ∈ A IMCF . Moreover, b max ≥ b ′ (a), for each a ∈ A IMCF . Therefore, M • a∈A IMCF c ′ (a) b ′ (a) • f IMCF (a) ≥ M b max • a∈A IMCF c ′ (a).
The computational time required by the algorithm defined in this proof is given by the cost of transforming I 1 into I 2 , that of transforming I 2 into I 3 , and that of solving I 3 . As the graph defined for We now analyze some special cases where the approximation bound can be improved. In the previous section, it has been shown that when ∆ ≤ 2, MCFMI is NP -hard in the unbounded case and it is polynomially solvable in the bounded case. Theorem 5.1 shows that even for fixed ∆ ≥ 3 MCFMI is not approximable within a constant approximation bound. Hence, we focus on the approximation for the unbounded case where ∆ ≤ 2. We give two results which show that, in the unbounded case, if ∆ = 1 or the input graph is a path, then MCFMI admits a FPTAS, while in the case that the input graph is a cycle the approximability of MCFMI remains open.

The following corollary gives an FPTAS in the case that ∆ = 1 and it follows from Theorem 4.4.

Corollary 5.4: In the unbounded case with ∆ = 1, MCFMI admits a (1 + ǫ)-approximation algorithm which requires O( k 2 ǫ ) time, for any ǫ > 0. Proof: It follows by applying the linear time algorithm A of Theorem 4.4 which requires O(k) time, and the algorithm from [START_REF] Gens | Computational complexity of approximation algorithms for combinatorial problems[END_REF] which provides a (1+ǫ)-approximation for M inKP in O( k 2 ǫ ) time. The following theorem gives an FPTAS in the case that the input graph is a path.

Theorem 5.5: In the unbounded case, if the input graph is a path, MCFMI admits a (2+ǫ)-approximation algorithm which requires O(|V | k 2 ǫ ) time, for any ǫ > 0. Proof: Let us denote the input path as a sequence of n nodes: s ≡ x 0 , x 1 , . . ., x n-1 ≡ t. We define an algorithm C as follows. It defines n -1 M inKP problems, each one arising from one different edge e i = {x i-1 , x i } of the path, 1 ≤ i ≤ n -1, by using the linear time algorithm A of Theorem 4.4. From Corollary 5.4, this implies that for each e i and for any ǫ > 0, a (1 + ǫ)-approximation for M inKP can be guaranteed. Algorithm C chooses, for each 1 ≤ i ≤ n -1, interfaces W i arising from the approximate solution of the related knapsack problem on edge e i , that is interfaces W i are activated on nodes x i-1 and x i .

For each 1 ≤ i ≤ n-1, let us denote as W * i ⊆ X(x i-1 , x i ), the sets of active interfaces in nodes x i-1 and x i in an optimal solution of MCFMI for the input path; and let W M K i ⊆ X(x i-1 , x i ) the sets of active interfaces in nodes x i-1 and x i in an optimal solution of the M inKP problem obtained by C for the input path.

Note that, for some i, the set W i ∩ W i+1 is not necessarily empty, which means that node x i uses a set of interfaces for communicating with both x i-1 and x i+1 . Thus, in this case, the cost paid for activating the interfaces used by x i is less than c(W i ) + c(W i+1 ) and the same holds for solutions W * i and W M K i . It follows that, for each 1 ≤ i ≤ n -1 the cost paid for activating interfaces in W i in nodes x i and x i-1 is at most 2c(W i ) and the overall cost of the solution provided by C is less than or equal to 2 n-1 i=1 c(W i ). As from Corollary 5.4 we are using in each edge a (1 + ǫ)-approximation algorithm for the knapsack problem, it follows that:

2 n-1 i=1 c(W i ) ≤ 2 n-1 i=1 (1 + ǫ)c(W M K i ). As W M K i
is an optimal solution for M inKP on edge e i which guarantees a bandwidth of

B, c(W M K i ) ≤ c(W * i ), for each 1 ≤ i ≤ n -1, and hence: 2(1 + ǫ) n-1 i=1 c(W M K i ) ≤ 2(1 + ǫ) n-1 i=1 c(W * i ) ≤ 2(1 + ǫ) n-2 i=1 c(W * i ∪ W * i+1 ) + c(W * n-1 ) ≤ 2(1 + ǫ)
OPT, where the two last inequalities follow from the fact that in an optimal solution the cost of activating interfaces for each node ǫ ′ ) time. The FPTAS provided directly implies the existence of a pseudo-polynomial-time algorithm for the case where the input graph is a path. This implies that, in this case, the problem is not NP -hard in the strong sense.

x i is c(W * i ∪ W * i+1 ) ≥ c(W * i ) and the overall cost is OPT = c(W * 1 ) + n-2 i=1 c(W * i ∪ W * i+1 ) + c(W * n-1 ). The complexity of C is O(n k 2 ǫ ) as it is composed of n -1 executions of algorithm A of Theorem 4.

VI. EXPERIMENTAL ANALYSIS

In this Section, we report the results of our experimental study on the approximation algorithm given in Theorem 5.2 which is denoted by ALG in the remainder of the section.

The experiments have been carried out on a workstation equipped with a 2.66 GHz processor (Intel Core2 Duo E6700 Box) and 8Gb RAM running Linux 2.6 kernel and Gcc compiler, version 4.3.5.

We implemented algorithm ALG by using the LEMON Graph Library [START_REF]LEMON graph library[END_REF] framework. In order to solve the IMCF instances required by ALG we used the Network Simplex algorithm [START_REF] Dantzig | Linear Programming and Extensions[END_REF] provided by LEMON as it is the most experimentally efficient in general cases.

A. Input data and executed tests.

Instances of MCFMI have been randomly generated by using two different models: The balls-into-bins [START_REF] Papadopoulos | Connectionless probabilistic (cop) routing: an efficient protocol for mobile wireless adhoc sensor networks[END_REF], [START_REF] Raab | balls into bins" -a simple and tight analysis[END_REF] and the Barabási-Albert power-law [START_REF] Albert | Emergence of scaling in random networks[END_REF] models.

The balls-into-bins model is used to simulate devices thrown at random in a two-dimensional space [START_REF] Papadopoulos | Connectionless probabilistic (cop) routing: an efficient protocol for mobile wireless adhoc sensor networks[END_REF]. In this model, each instance of MCFMI is made of a graph G BIB = (V BIB , E BIB ), a set of interfaces I BIB = {1, 2, . . . , k} along with cost and bandwidth functions c BIB , and b BIB , and two allocation functions W BIB : V BIB → 2 IBIB and X BIB : V BIB × V BIB → 2 IBIB . First, nodes in V BIB are generated and a uniformly random position in a unit size square is associated to each of them. From the "balls-into-bins" theory [START_REF] Raab | balls into bins" -a simple and tight analysis[END_REF], we know that throwing randomly n points in a unit square, the probability that no nodes are inside a circle of diameter d = γ log n n is smaller than n -γ 4 , hence, for γ > 4 and large n, this probability is very low. Therefore, to generate edges and interfaces we proceed as follows. For each interface i ∈ I BIB , the radius r i > 0 of the circle covered by interface i is generated uniformly at random in

1 |VBIB| , γ log(|VBIB|) |VBIB| -1
|VBIB| . In this way, interfaces cover a circle having an average diameter of γ log |VBIB| |VBIB| . Then function W BIB is defined by independently assigning the generated interfaces to nodes with probability 0.5. Given two nodes u, v ∈ V BIB , let (x u , y u ) and (x v , y v ) be their associated coordinates in the unit square. If (x ux v ) 2 + (y uy v ) 2 ≤ r i , for some i ∈ W BIB (u) ∩ W BIB (v), an edge {u, v} is added to E BIB and interface i is added to X BIB (u, v), i.e., X BIB (u, v) = W BIB (u) ∩ W BIB (v). In this way, for large values of |V BIB | and γ > 4, we have a high probability to obtain a connected network. Finally, functions c BIB and b BIB are defined as c BIB (i) = r α i and b BIB (i) = r β i , for each i ∈ I BIB and for suitable tuning parameter α, and β which are fixed to 1.5, and 2, respectively in the experiments. Source and target nodes are chosen as the nodes with the biggest Euclidean distance.

Barabási-Albert networks have been proven to model many real-world networks such as the Internet, the World Wide Web, citation graphs, and some social networks [START_REF]Statistical mechanics of complex network[END_REF]. A Barabási-Albert topology is generated by iteratively adding one node at a time, starting from a given connected graph with at least two nodes. A newly added node is connected to any other existing nodes with a probability that is proportional to the degree that the existing nodes already have. Hence, the more connected a node is, the more likely it is to receive new connections to the new node. This mechanism is known as preferential attachment and it has been observed in many realworld networks.

In this model, each generated instance of MCFMI is made of a graph G BA = (V BA , E BA ), a set of interfaces I BA = {1, 2, . . . , k} along with cost and bandwidth functions c BA , and b BA , and two allocation functions W BA : V BA → 2 IBA and X BA : V BA × V BA → 2 IBA . The graph generation algorithm works as follows. We start from a graph made of two nodes connected by an edge and add one node at a time. A new node v is connected to an existing node u with probability p(v, u) = deg (u) 2m , where deg(u) is the degree of node u before adding v and m is the number of edges that already exist when v is added. Interfaces I BA and related costs and bandwidth functions are generated in a way similar to the balls-into-bins model, that is, for each interface i ∈ I BA , a number r i is generated uniformly at random in 1 |VBA| , γ log(|VBA|)

|VBA|

-1 |VBA| , then c BA (i) and b BA (i) are set to c BA (i) = r α i and b BA (i) = r β i . Parameters γ, α, and β are set to 5, 1.5, and 2, respectively. For each edge {u, v} ∈ E BA , interface i ∈ I BA is added to X BA (u, v) with probability 0.5. For each node v, W BA (v) is induced by the interfaces associated in X BA (u, v) for each edge {u, v} incident to v. Source and target nodes are chosen at random among the generated nodes.

For each of the defined instances in both the models above, we considered four values of required flow equally distributed between the minimal bandwidth assigned to an interface b min and the maximum flow possible F max , computed by the algorithm given in Theorem 4.1. That is, we required a flow of b min + i • Fmax-bmin 3 , for i = 0, 1, 2, 3. In the remainder, we will not consider the case where the required flow is b min (i.e. i = 0) as in this case we are able to find an optimal solution to MCFMI by computing a cheapest path (see [START_REF] Kosowski | Exploiting Multi-Interface Networks: Connectivity and Cheapest Paths[END_REF]) connecting source and destination. When the considered instance is clear by the context, we denote Fmax-bmin 3 simply by δ. In order to measure the approximation ratio in the above settings, we need to know the optimal value of each MCFMI instance. As it is NP -hard to compute such value, we measured the ratio between the objective function value computed by our algorithm and a lower bound to the optimal value, obtaining an upper bound to the actual approximation ratio. In detail, we computed two lower bounds to the optimal value and then we use the maximum among them to get a better estimate of the approximation ratio. One lower bound is simply given by the optimal solution of the IMCF instance defined in ALG. Another lower bound to the optimal value is computed by observing that, if we relax the bandwidth constraints by increasing the bandwidth of an interface, we decrease the optimal value. Hence, we computed a lower bound to the optimal value as the optimal value of an instance obtained by setting the bandwidth of each interface to the maximum bandwidth assigned to the original instance. Such a value can be polynomially computed by using Corollary 5.3. II reports the size of the input data used in the experiments. We perform two kind of experiments: we fix k to 3, 6, and 9 and we let vary the number of nodes in the graphs from 50 to 1000; we fix the number of nodes in a graph to 10, 100, 1000, and 10000 and let k vary from 2 to 16. In each setting, we considered three values of required flow as explained above. For each of the above test configurations we performed 10 different experiments and, in the next section, we report average values and standard deviations.

B. Analysis of experimental results

The results of our experiments are reported in Fig. 5 shows the average values and the standard deviations of the computed upper bounds on the approximation ratio as a function of the number of nodes in the network |V BIB |, ranging from 50 to 1000, when the number of interfaces k is 9. The maximum value obtained is 3.12, achieved by an instance of 350 nodes and 5229 edges, when the required flow is F max . However, there are very few instances with an upper bound on the approximation ratio in [START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF][START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF]. In detail, for 3 instances it is in [START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF][START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF], for 71 instances it is in [START_REF]Maximum Flow and Minimum-Cost Flow in Multi-Interface Networks[END_REF][START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF], for 507 instances it is in (1, 2) and for all the other 19 instances it ensures the optimal value. On average, the upper bound is always smaller than 2.04. Moreover, we remind that these are only upper bounds to the real ratio. The curves do not show a strict dependency from the number of nodes |V BIB |. Conversely, there exists a small dependency from the required flow, that is the upper bound on the approximation ratio slightly increases with the required flow. The relevance of the obtained results is also given by the difference between the obtained upper bounds to the approximation ratios and the values of bmax M guaranteed by the theoretical analysis of Theorem 5.2. The value bmax M can be in fact very much higher than the experimented results. For instance, networks providing Fig. 5 shows an average value for b max larger than 10.000. This confirms the interest in studying the algorithm for practical instances in order to better understand its real performances. Fig. 6 shows the three curves when k = 3 and the other parameters are in the same setting as Fig. 5. As expected, the upper bound on the approximation ratio is improved here. This is due to the fact that reducing the number of interfaces implies that the possible overhead at each node is also reduced. In detail, the maximum upper bound on the approximation ratio obtained is 2.71, achieved by an instance of 400 nodes and 5311 edges, when the required flow is F max . The upper bound to the approximation ratio is in [2, 3) for 16 instances, in (1, 2) for 382 instances and the algorithm finds the optimum for the remaining 202 instances. Fig. 7 refers to the case where |V BIB | is fixed to 10000, and the number of interfaces k ranges from 2 to 16. Also in this case, the upper bound on the approximation ratio is very small. In detail, in the worst case it achieves 3.03. The curves show that there is not a strict dependency from the number of interfaces k, apart for small values of it (k ≤ 4) and that, also in this case, there exists a small dependency from the required flow. In fact, the upper bound on the approximation ratio slightly increases with the required flow.

We can conclude that, in graphs G BIB , the approximation ratio is always very small and it depends neither on the number of nodes nor on the number of interfaces, while there is a small dependency from the required flow. for graphs G BA . Also in these cases, the properties inferred for G BIB hold. In fact, the upper bound on the approximation ratio is small and it does not depend neither on the number of nodes nor on the number of interfaces. However, we can observe a worsening of the performances of the algorithm. In detail, although in most of the cases the approximation ratio is the same as for graphs G BIB there are some instances where it is much higher than the average. For instance, Fig. 8 shows a case where the average value is 2.65 and the standard deviation is 3.12 which is due to an instance where the upper bound on the approximation ratio is 11.80. Similar instances also appear in the other experiments on G BA . It is worth to note that the bad approximation bounds on these particular cases are mainly due to the bad estimation of the optimal value rather than to the behavior of ALG. In fact, it is known that graphs G BA have a small diameter [START_REF] Cohen | Scale-free networks are ultrasmall[END_REF] and hence both relaxations used for obtaining the lower bounds of the optimal value give a rather small value. In order to obtain a better estimation of the lower bound in graphs G BA , we performed a new set of tests with the same parameters as those of Fig.s 8-9 but in instances where the ratio between the maximal and the minimal bandwidth of the involved interfaces is upper bounded. These particular instances have a practical relevance because, in real cases, it is reasonable that the mentioned ratio is upper bounded. Such instances allow us to better estimate the optimal value because in such cases the two relaxations used can give a tight lower bound. Results for the case where the ratio between the maximal and the minimal bandwidth of an interface is at most 10 are given in Fig.s 10-11. Note that the values are similar to those of G BIB graphs.

Concerning the execution time of the algorithm, it goes from few microseconds in the smaller instances to some seconds in large instances made of 10000 nodes and 16 interfaces (see Table III). Hence, the algorithm is fast enough to be used in

VII. CONCLUSION

We have considered two fundamental optimization problems which take into account bandwidth constraints in Multi-Interface Networks: MFMI and MCFMI. In MFMI, we aim to establish the maximal bandwidth that can be guaranteed between two given nodes of the input network. In MCFMI, we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth of communication between two specified nodes. The obtained results have shown that MFMI is polynomially solvable while MCFMI is NP -hard. Polynomial exact and approximation algorithms for the general case and for special cases of MCFMI have been provided. Moreover, we experimentally analyzed algorithm ALG for MCFMI, showing that in practical cases it guarantees a low approximation ratio which allows us to use it in real-world.

Fig. 1 .

 1 Fig.1. The graph G and its transformation in the direct graph G ′ . W (s) = {1, 2}, W (v) = 1, 2, 3, W (t) = X(v, t) = {2, 3}, and X(s, v) = {1}.

Fig. 2 .

 2 Fig. 2. The subgraphs used in the proofs of Theorems 4.2 and 5.1.r

Fig. 3 .

 3 Fig. 3. The graph G in the transformation from X3C to MCFMI D .

In. :

 : An integer d ∈ Z + 0 and a set of n items, each one having weight w i ∈ Z + 0 and profit p i ∈ Z + 0 , i = 1, 2, . . . , n.Sol.: An allocation of variables yi ∈ {0, 1}, for i = 1, 2, . . . , n, such that n i=1 w i y i ≥ d Aim: Minimize n i=1 p i y i .M inKP problem is the corresponding minimization version of the Knapsack problem. In other words, the goal is to minimize the profits of the items that remain out of the knapsack. If x i , i = 1, 2, . . . , n, are the variables selecting the items for the classical knapsack problem and c ∈ Z + 0 its capacity, then the problem can be solved by means of M inKP , by setting d = n i=1 w ic and y i = 1x i , i = 1, 2, . . . , n.

Fig. 4 .

 4 Fig. 4. The graph G in the transformation from X3C to MCFMI D .

) = 1 ,

 1 c(3) = 0 and b(1) = n, b(2) = n, b(3) = 1. All the nodes in G have interface 1 apart from the central nodes of the n + |S| copies of the N (1) graph. All the nodes in N i (1) have interface 2, for each i = 1, 2, . . . , |S|. All the nodes in N j (1) have interface 3, for each j = 1, 2, . . . , n. Then,

Theorem 5 . 2 :

 52 There exists a polynomial time bmax Mapproximation algorithm for MCFMI which requires O(|V |k 2 + |E| + P A (|V |k 2 + |E|)) time.

  3 from I 2 by setting H = G ′ , Θ = B/M β(a) = b ′ (a)/M , and χ(a) = c ′ (a)/b ′ (a), for each a ∈ A. Given a feasible flow function f 3 for I 3 , a flow function f 2 for I 2 is obtained by multiplying f 3 by M , that is f 2 (a) = M • f 3 (a), for each a ∈ A. The feasibility of f 3 for I 3 clearly implies the feasibility of f 2 for I 2 .

5 . 3 :

 53 I 2 has O(|V |k) nodes and O(|V |k 2 + |E|) edges, the first and the second costs are O(|V |k 2 + |E|) while the third one is O(P A (|V |k 2 + |E|)). Corollary Let b ∈ Z + 0 . If b(i) = b for each i ∈ I, MCFMI is solvable within O(|V |k 2 +|E|+P A (|V |k 2 +|E|)). Proof: If b = 1, then the bmax M -approximation algorithm given in Theorem 5.2 optimally solves MCFMI. Otherwise, it is enough to solve the problem with required bandwidth of B = B b and bandwidth b(i) = 1, for each interface i. The computational time required by this algorithm is equal to that required by the algorithm defined in Theorem 5.2 B. Particular cases, ∆ ≤ 2

  4 which requires O(k) time, and n -1 executions of algorithm from [22] which requires O( k 2 ǫ ) time. By defining ǫ ′ = 2ǫ, Algorithm C provides a (2 + ǫ ′ )-approximated solution and requires O(|V | k 2

Fig. 6 .

 6 Fig. 6. Graphs G BIB : average upper bounds on the approximation ratios for |V BIB | ∈ {50, 100, . . . , 1000}, k = 3 and three values of required flow.

F

  s 5-11 and in Table III. For a better visualization, all the obtained values are normalized to |V BIB | for the experiments referring to graphs G BIB , and to |V BA | for the experiments referring to graphs G BA . This is equivalent to consider each instance graph G = (V, E) inside a |V | × |V | square instead of a unitary square. The figures show the average values and the standard deviations of the computed upper bound to the approximation ratio of our algorithm. Each figure contains three curves, one for each considered required flow. In particular, for each instance, we consider three possible values of required flow equally distributed in the interval {b min , . . . , F max }. Namely, the curves refer to b min + δ, F maxδ and F max , as for b min we can compute the optimal value.

Fig.

  Fig.5shows the average values and the standard deviations of the computed upper bounds on the approximation ratio as a function of the number of nodes in the network |V BIB |, ranging from 50 to 1000, when the number of interfaces k is 9. The maximum value obtained is 3.12, achieved by an instance of 350 nodes and 5229 edges, when the required flow is F max . However, there are very few instances with an upper bound on the approximation ratio in[START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF][START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF]. In detail, for 3 instances it is in[START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF][START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF], for 71 instances it is in[START_REF]Maximum Flow and Minimum-Cost Flow in Multi-Interface Networks[END_REF][START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF], for 507 instances it is in[START_REF] Angelo | Bandwidth Constrained Multi-Interface Networks[END_REF][START_REF]Maximum Flow and Minimum-Cost Flow in Multi-Interface Networks[END_REF] and for all the other 19 instances it ensures the optimal value. On average, the upper bound is always smaller than 2.04. Moreover, we remind that these are only upper bounds to the real ratio. The curves do not show a strict dependency from the number of nodes |V BIB |. Conversely, there exists a small dependency from the required flow, that is the upper bound on the approximation ratio slightly increases with the required flow. The relevance of the obtained results is also given by the difference between the obtained upper bounds to the approximation ratios and the values of bmax M guaranteed by the theoretical analysis of Theorem 5.2. The value bmax M can be in fact very much higher than the experimented results. For instance, networks providing Fig.5shows an average value for b max larger than 10.000. This confirms the interest in studying the algorithm for practical instances in order to better understand its real performances. Fig.6shows the three curves when k = 3 and the other parameters are in the same setting as Fig.5. As expected, the upper bound on the approximation ratio is improved here. This is due to the fact that reducing the number of interfaces implies that the possible overhead at each node is also reduced. In detail, the maximum upper bound on the approximation ratio obtained is 2.71, achieved by an instance of 400 nodes and 5311 edges, when the required flow is F max . The upper bound to the approximation ratio is in [2, 3) for 16 instances, in (1, 2) for 382 instances and the algorithm finds the optimum for the remaining 202 instances. Fig.7refers to the case where |V BIB | is fixed to 10000, and the number of interfaces k ranges from 2 to 16. Also in this case, the upper bound on the approximation ratio is very small. In detail, in the worst case it achieves 3.03. The curves show that there is not a strict dependency from the number of interfaces k, apart for small values of it (k ≤ 4) and that, also in this case, there exists a small dependency from the required flow. In fact, the upper bound on the approximation ratio slightly increases with the required flow.We can conclude that, in graphs G BIB , the approximation ratio is always very small and it depends neither on the number of nodes nor on the number of interfaces, while there is a small dependency from the required flow. Fig.s 8 and 9 show the experimental results in the same settings as Fig.s 5 and 7for graphs G BA . Also in these cases, the properties inferred for G BIB hold. In fact, the upper bound on the approximation ratio is small and it does not depend neither on the number of nodes nor on the number of interfaces. However, we can observe a worsening of the performances of the algorithm. In detail, although in most of the cases the approximation ratio is the same as for graphs G BIB there are some instances where it is much higher than the average. For instance, Fig.8shows a case where the average

Fig.s 8

 8 Fig.5shows the average values and the standard deviations of the computed upper bounds on the approximation ratio as a function of the number of nodes in the network |V BIB |, ranging from 50 to 1000, when the number of interfaces k is 9. The maximum value obtained is 3.12, achieved by an instance of 350 nodes and 5229 edges, when the required flow is F max . However, there are very few instances with an upper bound on the approximation ratio in[START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF][START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF]. In detail, for 3 instances it is in[START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF][START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF], for 71 instances it is in[START_REF]Maximum Flow and Minimum-Cost Flow in Multi-Interface Networks[END_REF][START_REF] Bahl | Reconsidering wireless systems with multiple radios[END_REF], for 507 instances it is in[START_REF] Angelo | Bandwidth Constrained Multi-Interface Networks[END_REF][START_REF]Maximum Flow and Minimum-Cost Flow in Multi-Interface Networks[END_REF] and for all the other 19 instances it ensures the optimal value. On average, the upper bound is always smaller than 2.04. Moreover, we remind that these are only upper bounds to the real ratio. The curves do not show a strict dependency from the number of nodes |V BIB |. Conversely, there exists a small dependency from the required flow, that is the upper bound on the approximation ratio slightly increases with the required flow. The relevance of the obtained results is also given by the difference between the obtained upper bounds to the approximation ratios and the values of bmax M guaranteed by the theoretical analysis of Theorem 5.2. The value bmax M can be in fact very much higher than the experimented results. For instance, networks providing Fig.5shows an average value for b max larger than 10.000. This confirms the interest in studying the algorithm for practical instances in order to better understand its real performances. Fig.6shows the three curves when k = 3 and the other parameters are in the same setting as Fig.5. As expected, the upper bound on the approximation ratio is improved here. This is due to the fact that reducing the number of interfaces implies that the possible overhead at each node is also reduced. In detail, the maximum upper bound on the approximation ratio obtained is 2.71, achieved by an instance of 400 nodes and 5311 edges, when the required flow is F max . The upper bound to the approximation ratio is in [2, 3) for 16 instances, in (1, 2) for 382 instances and the algorithm finds the optimum for the remaining 202 instances. Fig.7refers to the case where |V BIB | is fixed to 10000, and the number of interfaces k ranges from 2 to 16. Also in this case, the upper bound on the approximation ratio is very small. In detail, in the worst case it achieves 3.03. The curves show that there is not a strict dependency from the number of interfaces k, apart for small values of it (k ≤ 4) and that, also in this case, there exists a small dependency from the required flow. In fact, the upper bound on the approximation ratio slightly increases with the required flow.We can conclude that, in graphs G BIB , the approximation ratio is always very small and it depends neither on the number of nodes nor on the number of interfaces, while there is a small dependency from the required flow. Fig.s 8 and 9 show the experimental results in the same settings as Fig.s 5 and 7for graphs G BA . Also in these cases, the properties inferred for G BIB hold. In fact, the upper bound on the approximation ratio is small and it does not depend neither on the number of nodes nor on the number of interfaces. However, we can observe a worsening of the performances of the algorithm. In detail, although in most of the cases the approximation ratio is the same as for graphs G BIB there are some instances where it is much higher than the average. For instance, Fig.8shows a case where the average

Fig. 8 .

 8 Fig. 8. Graphs G BA : average upper bounds on the approximation ratios for |V BA | ∈ {50, 100, . . . , 1000}, k = 9 and three values of required flow.

Fig. 9 .

 9 Fig. 9. Graphs G BA : average upper bounds on the approximation ratios for |V BA | = 10000, k ∈ {2, 4, . . . , 16} and three values of required flow.

Fig. 10 .

 10 Fig. 10. Graphs G BA when bmax b min is bounded: average upper bounds on the approximation ratios in the same setting as Fig. 8.

F

TABLE I COMPLEXITY

 I RESULTS ACHIEVED FOR MCFMI BY VARYING ON THE MAXIMUM DEGREE ∆ AND THE NUMBER OF AVAILABLE INTERFACES k.

	∆	k	Complexity
	∆ = 1	Fixed Unbounded NP-hard (equiv. MinKnapsack), (1 + ǫ)-apx in Optimally solvable in O(1) time O( k 2 ǫ )
	∆ = 2	Fixed	Optimally solvable in O(|V |)

TABLE II SIZE

 II OF THE INPUT DATA. BIB : average upper bounds on the approximation ratios for |V BIB | ∈ {50, 100, . . . , 1000}, k = 9 and three values of required flow.

	Graph				|V |				k
	Balls-into-bins	{50, 100, . . . , 1000} {10, 100, 1000, 10000}	{3, 6, 9} {2, 4, . . . , 16}
	Barabási-Albert	{50, 100, . . . , 1000} {10, 100, 1000, 10000}	{3, 6, 9} {2, 4, . . . , 16}
	F max -δ b min + δ Fig. 5. Graphs G F max 2.6 2.4 2.2 2
	1.8
	1.6
	1.4
	1.2
	1
	0.8
	0	100	200	300	400	500	600	700	800	900	1000
						|V BIB |

Table

  max F maxδ b min + δ Fig. 7. Graphs G BIB : average upper bounds on the approximation ratios for |V BIB | = 10000, k ∈ {2, 4, . . . , 16} and three values of required flow.

	2.2
	2
	1.8
	1.6
	1.4
	1.2
	1
	0.8
	0.6
	0	100	200	300	400	500	600	700	800	900	1000
					|V BIB |
	2.8 2.6 2.4 2.2						b min + δ F max -δ F max
	2
	1.8
	1.6
	1.4
	1.2
	1
	0.8
	2	4		6	8		10	12	14	16
						k

  max F maxδ b min + δ Fig. 11. Graphs G BA when bmax b min is bounded: average upper bounds on the approximation ratios in the same setting as Fig. 9.

	2.4
	2.2
	2
	1.8
	1.6
	1.4
	1.2
	1
	0.8
	0	100	200	300	400	500	600	700	800	900	1000
						|V BA |
	2.8 2.6 2.4 2.2						b min + δ F max -δ F max
	2
	1.8
	1.6
	1.4
	1.2
	1
	0.8
	2	4		6	8		10	12	14	16
						k
	large scale networks.