Polylogarithmic Approximation for Covering and Connecting Multi-Interface Networks Michał Szyfelbein∗
Camille Richer†
arXiv:2605.06899v1 [cs.DS] 7 May 2026
Abstract We study problems related to connecting multi-interface networks of wireless devices. These problems can be modeled using graphs, where vertices represent the devices and edges represent potential communication links. Each vertex can activate multiple interfaces, and a connection between two vertices is established if they share at least one common active interface. We consider the heterogeneous setting, where activating an interface induces a cost that depends on the type of interface and on the vertex that activates it. We consider two problems arising in multi-interface networks: Coverage and Connectivity. In the Coverage problem, every connection defined in the network must be established, while in the Connectivity problem, groups of terminals specified in the input should be connected. The solution should also minimize either the maximum cost incurred by a vertex or the total cost incurred by all vertices. In this work we are interested in approximating the former of the two cost criterions. We model both problems using Integer Linear Programming (ILP) and we design approximation algorithms based on a randomized rounding of the solution of the linear programming relaxation. For the Coverage problem, this yields an O(log m)-approximation algorithm, which is tight, since the problem generalizes Set-Cover. This improves upon the O(b · log n)approximation algorithm, where b is a certain graph parameter which can be as large as Ω(n) [Algorithmica ’12]. The same relaxation can also be used to get an k-approximation algorithm, where k is the number of different interfaces. This generalizes a similar result for the uniform cost case. For the Connectivity problem, we obtain an O(log2 m)-approximation algorithm, which is the first non-trivial approximation algorithm for this problem. The algorithm is based on a similar LP relaxation with additional cut constraints to ensure connectivity. The rounding procedure is similar to the one for the Coverage problem but requires a more careful analysis to ensure that the connectivity constraints are satisfied.
1
Introduction
Designing Internet of Things (IoT) networks often demands establishing connection between large number of devices, which can be achieved by activating communication interfaces at each of them. However, the devices present in the network may vary according to the type of interfaces they have available and the amount of resources a given interface consumes. For example some device may be able to utilize Bluetooth and Wi-Fi connections, while the others may provide Zigbee and Z-Wave interfaces. Since IoT devices are typically resource-constrained, it may be desirable to try to establish every relevant connection, while minimizing the amount of resources required to do so. We model the above problem as a graph problem. Every device in the network is represented by a vertex with a set of labels encoding its available interfaces. Two devices can communicate if they share a common available interface and are connected by an edge, representing that they are within communication range. A connection is established between two adjacent devices whenever ∗
Gdańsk University of Technology, Poland. [email protected]. ORCID: 0009-0009-9894-9671 Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE. [email protected]. ORCID: 0009-0000-3636-6571 †
1
Colors represent available interfaces
Colors represent active interfaces
Figure 1: On the left, an instance of the Coverage problem, and on the right a covering assignment for that instance (if an edge is covered by several interfaces, only one is represented).
Contours represents terminal groups (double for groupe 1
Colors represent active interfaces: only bold edges are
and triple for group 2)
covered
Figure 2: On the left, an instance of the Connectivity problem with two terminal groups, and on the right a connecting assignment for that instance. they share a common active interface. We want to find an assignment of active interfaces to vertices so that we ensure either the Coverage or Connectivity property. In the Coverage problem, we wish to establish every possible direct connection in the network which means that both endpoints of every edge must share a common activated interface (see Figure 1 for an example). In the Connectivity problem, we are additionally given a collection of disjoint vertex subsets called terminals, and we require each terminal group to be (not necessarily directly) connected in the subgraph induced by active interfaces (see Figure 2 for an example). In both problems, we assume that activating an interface induces a cost that depends on the type of interface and on the vertex that activates it. The goal is to minimize the max cost, i. e., the maximum cost of activated interfaces across all vertices.
1.1
Related Work
In the following, let k denote the number of different interfaces across the network, n the number of vertices in the input graph, m the number of edges, ∆ the maximum degree, cmax the maximum cost and cmin the minimum cost of an interface. In the homogeneous setting, the costs only depend on the interface while in the heterogeneous case they depend on the interface and on the vertex.
2
Coverage Problem. The algorithmic study of problems in multi-interface networks started with the problem of covering a multi-interface networks, introduced in Caporuscio et al. [6]. This problem has been studied in the homogeneous setting only, both for min-sum [12] and min-max [7] objective functions. The min-sum, unit cost variant is APX-hard for any constant k ≥ 3, and is hard to approximate √ within a O(ln k) factor. On the positive side, it has a min{k − 1, n(1 + ln n)}-approximation [12]. The min-max variant with uniform costs is NP-Hard for any constant ∆ ≥ 5, k ≥ 16, and it is not approximable within a η ln ∆ factor for some constant η even on trees. On the positive side, with homogeneous costs it admits a (ln ∆ + 1 + b · min{cmax , ln ∆ + 1})-approximation, where b is a parameter that depends on the structural properties of the input graph and is bounded by many other graph structural parameters such as treewidth, arboricity or maximum degree. It cmax cmax )-approximation and a ( ∆ also has a (1 + (k − 2) 2c 2 cmin )-approximation [7]. min Connectivity Problem. The problem of connecting a multi-interface network was introduced by Kosowski et al. [14]. It was first studied in the homogeneous setting and in the special case where all vertices are terminals, both for the min-sum [14] and the min-max objective functions [7]. The aforementioned min-sum variant is APX-hard for k ≥ 2, ∆ ≥ 4 and unit costs already, but has a 2-approximation [14]. This result was improved by Athanassopoulos et al. [4] to a randomized ( 32 + ϵ)-approximation for any constant ϵ. Moreover, this approximation algorithm applies to the more general problem where for each interface, the set of edges that it can cover is specified in the input. The min-max variant where all vertices are terminals and costs are homogeneous is NP-Hard for any constant ∆ ≥ 3, k ≥ 10 and for unit costs. Similarly to the coverage problem, it is not cmax approximable within a η ln n factor even for unit costs, but has simple (1 + (k − 2) 2c )- and min ∆ cmax 2 cmin -approximations [7]. Athanassopoulos et al. [4] expand the study of the min-sum variant where there are multiple terminal groups. They provide a randomized 4-approximation for it. They also initiate the study of this problem in the heterogeneous setting. They show that for heterogeneous costs, the min-sum variant is hard to approximate within o(ln n) even when all vertices are terminals, but the min-sum group connectivity heterogeneous case admits a O(ln n)-approximation. Other Multi-interface Problems. There has been some work on the study of the coverage problem from the perspective of parameterized complexity, possibly with an additional constraint on the maximum number of active interfaces in a vertex [2, 1, 5], yielding efficient algorithms in some graph classes. Some papers also study other problems in multi-interface networks, like cheapest path [14], matchings [13], or flow problems [8].
1.2
Our contribution and techniques
We study the approximability of the Coverage and Connectivity problems minimizing the max cost under heterogeneous cost functions. We give a set-cover-style LP relaxation for the Coverage problem and show that treating the resulting fractional solution as a probability distribution and applying a randomized rounding procedure yields an O(log m)-approximation. This is the first logarithmic approximation for this problem with heterogeneous costs, and it matches the previously known lower bound of Ω(log n) for stars with unit costs [7]. It also improves the previously best known O(ln ∆ + b · min{ln ∆, cmax })-approximation (for some graph input parameter b), limited to the homogeneous case [7]. A simpler deterministic rounding of cmax this LP gives a k-approximation, asymptotically generalizing the 1 + (k − 2) 2c -approximation min for the min-max variant with homogeneous costs[7].
3
For the Connectivity problem, we extend the LP by adding flow-based cut constraints encoding group connectivity. Our rounding procedure is similar to the one for the Coverage problem, however, this time the process is iterative and the algorithm proceeds until all terminal groups are connected. Each iteration is randomized and we show that in expectation, in each such round the algorithm covers a significant fraction of edges of some graph which connects all group terminals. This yields an O log2 m -approximation algorithm, which is the first non-trivial approximation algorithm for this problem. The rest of the paper is structured as follows: In Section 2, we give notations, define the problems formally, and recall the elements of probability theory useful for the analysis of our algorithms. We also describe the preprocessing required for our randomized algorithms for the Coverage and Connectivity problems to work. In Section 3, we present the O(log m)approximation and the k-approximation algorithms for the Coverage problem. In Section 4, we present the O log2 m -approximation algorithm for the Connectivity problem. We conclude with a short discussion on open questions and future work.
2
Preliminaries
Let G = (V, E) be a connected simple graph. Let [k] be the set of different types of interfaces across the network and let λ : V → 2[k] be a function that assigns to each vertex v ∈ V its set of available interfaces, such that for each edge uv ∈ E, λ(u) ∩ λ(v) = ̸ ∅. An assignment of active interfaces is a function λA : V → 2[k] such that λA (v) ⊆ λ(v) for every v ∈ V . We say that an edge uv ∈ E is covered if λA (u) ∩ λA (v) = ̸ ∅. We denote by cov(λA ) = {uv ∈ E : λA (u) ∩ λA (v) = ̸ ∅} the set of edges covered by λA , and by GA the subgraph of G with edge set cov(λA ). In the Coverage problem, we wish to find an assignment of active interfaces λA such that GA = G. We call such an assignment a covering assignment. In the Connectivity problem, we are additionally given p ≥ 1 pairwise disjoint groups of terminals U1 , U2 , . . . , Up ⊆ V and we wish to find an assignment of active interfaces λA such that for every r ∈ [p], S Ur ⊆ V (GA ) and all vertices in Ur lie in the same connected component of GA . Vertices in V \ pr=1 Ur may be used as Steiner vertices. We call such an assignment a connecting assignment. The special case p = 1 with U1 = V corresponds to requiring that GA is a connected spanning subgraph of G. We are also given a cost function c : [k] × V → N≥0 , which denotes the cost of activating the interface i ∈ [k] at the vertex v ∈ V . As a convention, we assume that c(i, v) = ∞ if i ∈ / λ(v). For an assignment λA , define the cost of v as: X cost(v, λA ) = c(i, v) . i∈λA (v)
The max-cost of an assignment λA is defined as: cost(λA ) = max cost(v, λA ) . v∈V
The goal of the min-max assignment problem is to find an assignment λA that minimizes cost(λA ) while ensuring either Coverage or Connectivity. We denote by OPT the cost of an optimal solution to the problem at hand. We will refer to the min-max covering assignment problem as Coverage and the min-max connecting assignment problem as Connectivity.PNote that there also exists a min-sum variant of these problems, where the goal is to minimize v∈V cost(v, λA ) instead of cost(λA ).
2.1
Probabilistic tools
Since our algorithms are randomized, we will need to use the following probability facts in the analysis. 4
Theorem 2.1 (Markov’s Inequality). Let X be a non-negative random variable and a > 0. Then: Pr[X ≥ a] ≤
E[X] . a
Theorem 2.2 ((Weighted) Chernoff Bound). Let X1 , X2 , . . . , Xn be independent random variables taking values in [0, 1], let w1 , w2 , . P . . , wn be non-negative weights, such that for every i ∈ [n] we have that wi ∈ [0, 1]. Let X = ni=1 wi · Xi and let µ = E[X]. Then for every δ1 > 0 and δ2 ∈ (0, 1) we have that: Pr(X ≥ (1 + δ1 ) · µ) ≤
e δ1 (1 + δ1 )1+δ1
µ
Pr(X ≤ (1 − δ2 ) · µ) ≤
e−δ2 (1 − δ2 )1−δ2
µ .
The proof of the above fact follows the proof of the standard Chernoff bound and we include it in Section A for completeness.
2.2
Preprocessing
Due to technical reasons, before applying our algorithms we perform some preprocessing on the input instance (for both the Coverage and Connectivity problems). The goal of this preprocessing is to ensure that we have a good lower bound on OPT and to distinguish between two types of vertices, which will come in handy in the analysis of our algorithms. We describe this preprocessing in the following. Scaling of the costs Firstly, we create a polynomial number of instances, in such a way that for at least one of them we have a good lower bound on OPT. For convenience sake, we will allow the costs to be rational numbers and scale them appropriately so that all of them lie in the interval [0, 1]. To do so, by testing consecutive powers of 2, we guess the smallest number b, such that the costliest activated interface in the optimal solution has cost at most 2b . The number of such guesses is C, where C = log maxv∈V (G),i∈λ(v) {c(i, v)} which is polynomial in the input size. If either some edge cannot be covered by interfaces of cost at most 2b , or there is no vertex v and interface i ∈ λ(v), such that c(i, v) ∈ [1/2, 1], then we discard such guess. Otherwise, for each vertex v ∈ V , we temporarily remove from λ(v) all of the interfaces with cost larger than 2b . Let Cb = maxv∈V (G),i∈λ(v) {c(i, v)} (in this newly created instance). We normalize the costs of remaining interfaces by dividing them by Cb , so that the largest cost is exactly 1. We get that for the right guess of Cb , OPT ≥ Cb ≥ 1/2. Cheap and expensive vertices Having established the scaling of costs, Pwe now consider two types of vertices, with respect to the new costs. For a given vertex v ∈ V , if i∈λ(v) c(i, v) ≤ 1, then we can safely assume v activates all interfaces in λ(v), since the cost of activating all of them is at most 1 and thus upper bounded by 2 · OPT. We call such vertices cheap. The remaining vertices are called expensive. Note that for every expensive vertex v, we can assume that cost(λA , v) ≥ 1, since such an assumption will always result in an increase of cost of at most 2 · OPT which does not impact the asymptotical guarantee of our procedures. Finding the solution Since our algorithms are randomized we also need to take care of the probability of failure. We wish to ensure, that with high probability, for all values of b we will find a good solution. To do so, for each guess of b, we repeat the randomized procedure K = ⌈logm (C) + 1⌉ times (which is polynomial). The algorithm is as follows:
5
Algorithm 1: Preprocessing algorithm 1 λA (v) ← ∅ for every v ∈ V . 2 for b ∈ {0, . . . , C} {c(i, v)} do 3
4
5 6 7 8 9
For the remainder of this iteration discard interfaces with cost larger than 2b and divide all remaining costs by maxv∈V (G),i∈λ(v) {c(i, v)}. if there is no solution for this new instance or there is no vertex v and interface i ∈ λ(v), such that c(i, v) ∈ [1/2, 1] then continue for j ∈ [K] do λ′A ← the output of the randomized procedure for the scaled-cost instance. if cost(λ′A ) < cost(λA ) and λ′A is a covering/connecting assignment then λA ← λ′A .
10 return {λA (v)}v∈V .
Assuming that the probability of failure of the randomized procedure is at most O(1/m), we 1 K get that for each b, the probability of failure after K iterations is at most O 1/m = O mC . Since there are C guesses for b, applying the union bound over all of them we get that the probability that there exists some value of b, for which the algorithm will fail is at most O(1/m). In particular, this also holds for the right guess of b.
3
Approximation algorithms for the coverage problem
In this section, we consider the Coverage problem with heterogeneous costs. According to the preprocessing, we assume that interface costs are in [0, 1] and OPT ≥ 1/2. The considered problem is formalized below: Coverage Input: A connected simple graph G = (V, E), available interfaces λ : V → 2[k] , a cost function c : [k] × V → [0, 1]. Task: Find a covering assignment λA minimizing cost(λA ). The idea behind our ILP formulation and the algorithms is inspired by the rounding procedure known for Set Cover [15] and related problems [3].
3.1
ILP formulations of the Coverage problem
We start with the ILP formulation of the Coverage problem. Let xi,v be a binary variable that is 1 iff the interface i ∈ λ(v) is assigned to vertex v ∈ V . If a given vertex v is a cheap, then without large cost increase we canP force xi,v = 1, for every i ∈ λ(v). Otherwise, if a vertex v is expensive, we can assume that i∈λ(v) xi,v · c(i, v) ≥ 1, which corresponds to the fact that
6
cost(λA , v) ≥ 1. Thus, we can write the following ILP formulation of the Coverage problem: min M X c(i, v) · xi,v ≤ M s.t.
∀v ∈ V
(1)
i∈λ(v)
X
min{xi,u , xi,v } ≥ 1 ∀uv ∈ E
(2)
i∈λ(u)∩λ(v)
( P xi,v = 1 ∀i ∈ λ(v) if i∈λ(v) c(i, v) < 1 P i∈λ(v) c(i, v) · xi,v ≥ 1 otherwise
∀v ∈ V
xi,v ∈ {0, 1} ∀v ∈ V, i ∈ λ(v)
(3) (4)
Constraints (1) enforce that the cost of each vertex does not exceed the global cost M . Constraints (2) ensure that for every edge uv ∈ E(G), there exists a common activated interface. Constraints (3) encode the assumption that for every cheap vertex, all of its interfaces are activated, while for every expensive vertex, the cost of activated interfaces is at least 1. Finally, constraints (4) require the solution to be integral. Note that the above formulation is not linear due to constraints (2). However, by adding additional variables zi,uv , we can linearize constraints P (2) by replacing them with the constraints i∈λ(u)∩λ(v) zi,uv ≥ 1 together with zi,uv ≤ xi,u and zi,uv ≤ xi,v for every i ∈ λ(u) ∩ λ(v) and uv ∈ E. Thus, we can solve the LP relaxation of this formulation in polynomial time.
3.2
Warmup: A k-approximation algorithm
We begin by showing that a simple rounding of the LP solution can be used to obtain a kapproximation. Note that for this simple algorithm the preprocessing is not necessary, which makes it easily adaptable for the min-sum variant of the Coverage problem (assuming the ILP is appropriately changed). Algorithm 2: k-approximation algorithm 1 Solve the LP relaxation and obtain a fractional solution {xi,v }i∈λ(v),v∈V . 1 2 Set λA (v) ← {i ∈ λ(v) : xi,v ≥ k }, for every v ∈ V . 3 return {λA (v)}v∈V .
Theorem 3.1. Algorithm 2 is a k-approximation algorithm for the Coverage problem. Proof. Consider an edge uv ∈ E. By averaging, there exists an interface i ∈ λ(u) ∩ λ(v) such that min{xi,u , xi,v } ≥ k1 . Thus, i ∈ λA (u) ∩ λA (v) so λA isPa covering assignment. P Moreover, since 1 xi,v ≥ k for every i ∈ λA (v), we have that P c(λA (v)) = i∈λA (v) c(i, v) ≤ k · i∈λA (v) c(i, v) · xi,v . Thus, we have cost(λA ) ≤ k · maxv∈V i∈λ(v) c(i, v) · xi,v ≤ k · OPT.
3.3
An O(log m)-approximation algorithm for the Coverage problem
In order to extract an integral solution with quality independent of k, we employ a randomized procedure. For each interface type i ∈ [k], we draw a uniformly random threshold ti ∈ [0, 1] and activate the interface at a vertex if the corresponding variable scaled up by a factor of O(log m) exceeds ti . The procedure is formalized by the following pseudocode. Algorithm 3: O(log m)-approximation algorithm for the Coverage problem 1 Solve the LP relaxation and obtain a fractional solution {xi,v }i∈λ(v),v∈V . 2 Pick independent uniformly random thresholds ti ∈ [0, 1], for each i ∈ [k]. 3 λA (v) ← {i ∈ λ(v) : 2 ln m · xi,v ≥ ti }, for every v ∈ V . 4 return {λA (v)}v∈V .
7
Theorem 3.2. Algorithm 3 is an O(log m)-approximation algorithm for the Coverage problem which succeeds with high probability. Proof. Firstly, we claim that the algorithm indeed returns a feasible solution: Lemma 3.3. With high probability, Algorithm 3 returns an assignment λA , such that for every edge uv ∈ E, λA (u) ∩ λA (v) ̸= ∅. Proof. Consider an edge uv ∈ E. We have: Y Pr[λA (u) ∩ λA (v) = ∅] =
Pr[ti > 2 ln m · min{xi,u , xi,v }]
i∈λ(u)∩λ(v)
=
Y
{1 − 2 ln m · min{xi,u , xi,v }}
i∈λ(u)∩λ(v)
≤
Y
exp {−2 ln m · min{xi,u , xi,v }}
i∈λ(u)∩λ(v)
= exp −2 ln m ·
X i∈λ(u)∩λ(v)
≤ exp {−2 ln m} =
min{xi,u , xi,v }
1 m2
By applying the union bound over all m edges we get that the algorithm returns a covering 1 assignment with probability at least 1 − mm2 = 1 − m . Now, we also wish to show that the approximation factor achieved by our algorithm is upper bounded by O(log m). We have the following lemma: Lemma 3.4. Algorithm 3 returns a solution of cost at most 6 ln m · OPT with high probability. Proof. Fix a vertex v ∈ V . We want to show that with high probability, the cost of v is at most 6 ln m times the cost of v in the fractional solution. If v is cheap, then the cost of activating all interfaces at v is at most 1, so the claim holds. Assume that v is expensive. By Xv,i denote the random P variable that is 1 if 2 ln m · xi,v ≥ ti and 0 otherwise. Then we can write cost(v, λA ) = i∈λ(v) c(i, Pv) · Xv,i . We have: E[Xv,i ] = Pr[i ∈ λA (v)] = 2 ln m · xi,v . Thus, E[cost(v, λA )] = 2 ln m · i∈λ(v) c(i, v) · xi,v . By applying the Chernoff bound with δ = 2 we get that 2 E[cost(v,λA )] e 1 Pr[cost(v, λA ) ≥ 3 · E[cost(v, λA )]] ≤ ≤ exp {−E[cost(v, λA )]} ≤ 2 27 m P where the last inequality is by using the fact that, i∈λ(v) c(i, v) · xi,v ≥ 1. By applying the union bound over all n vertices we P get that with probability at least 1 − mn2 ≥ 1 − m+1 for m2 every v ∈ V , cost(v, λA ) ≤P 6 ln m · i∈λ(v) c(i, v) · xi,v . Thus, with high probability we have cost(λA ) ≤ 6 ln m · maxv∈V i∈λ(v) c(i, v) · xi,v ≤ 6 ln m · OPT. Combining the above lemmas gives the desired result.
4
Approximation algorithm for the Connectivity problem
In this section we consider the Connectivity problem with heterogeneous costs. We again assume that the instance is preprocessed, so we have that OPT ≥ 1/2.
8
Connectivity Input: A connected simple graph G = (V, E), available interfaces λ : V → 2[k] , a cost function c : [k] × V → [0, 1], pairwise disjoint groups of terminals U1 , . . . , Up ⊆ V . Task: Find a connecting assignment λA minimizing cost(λA ).
4.1
ILP formulation of the Connectivity problem
We use a similar ILP to model the Connectivity problem, however we use additional flow variables to encode the connectivity requirement. The xi,v variables are defined as before. For each edge e, we add a variable ye which is 1 iff the edge e is covered by the solution. For any S ⊆ V , let δ(S) denote the set of edges with exactly one endpoint in S. Connectivity within each group Ur is enforced via the cut constraints: for every r ∈ [p] and every cut (S, V \ S) that separates at least one pair P of terminals in Ur , there needs to be at least one covered edge crossing the cut. Let y(δ(S)) = e∈δ(S) ye . We can formulate the Connectivity problem as follows: min M X s.t. c(i, v) · xi,v ≤ M
∀v ∈ V
(5)
i∈λ(v)
X
min{xi,u , xi,v } ≥ yuv
∀uv ∈ E
(6)
i∈λ(u)∩λ(v)
( P xi,v = 1 ∀i ∈ λ(v) if i∈λ(v) c(i, v) < 1 P i∈λ(v) c(i, v) · xi,v ≥ 1 otherwise
∀v ∈ V
y(δ(S)) ≥ 1 ∀r ∈ [p], ∀S ⊂ V : S ∩ Ur ̸= ∅, (V \ S) ∩ Ur ̸= ∅
(7) (8)
xi,v ∈ {0, 1} ∀v ∈ V, i ∈ λ(v) yuv ∈ {0, 1} ∀uv ∈ E
(9)
Observe that the above ILP has an exponential number of constraints, but we can solve its LP relaxation in polynomial time using the ellipsoid method and a separation oracle for the cut constraints, which can be implemented using a max-flow algorithm.
4.2
An O(log2 m)-approximation algorithm for the Connectivity problem
Obtaining an integral solution for the Connectivity problem requires a more careful rounding procedure than for the Coverage problem. We wish to ensure that at least one subgraph which connects all terminal groups is covered by the assignment returned by the algorithm. To do so, we start by randomly sampling edges according to the y-variables of the fractional solution, so that with high probability, the sampled subgraph H contains a subgraph spanning and connecting each terminal group. To achieve this goal, we set the probability of choosing e to be pe = min{1, 4 ln m · ye }. Then, the goal of the algorithm becomes covering H. To do so, we repeat the following process: we draw uniformly random thresholds ti for each type of interface i ∈ [k], and activate i at any vertex for which 4 ln m · xi,v ≥ ti . Intuitively, each such iteration costs O(log m · OPT) in expectation and covers Ω(1) fraction of edges of H. After repeating this for a fixed number of T = O(log m) rounds, it can be shown that the algorithm covers all edges of H almost surely. The formal description of the algorithm is given by the following pseudocode.
9
Algorithm 4: O log2 m -approximation algorithm for the Connectivity problem 1 Solve the LP relaxation and obtain a fractional solution {xi,v }i∈λ(v),v∈V , {yuv }uv∈E . 2 For every edge e ∈ E, pe ← min{1, 4 ln m · ye }. 3 With probability pe set Ye ← 1, otherwise set Ye ← 0. 4 Let H be the subgraph of G induced by the edges e such that Ye = 1. 2 ln m 5 T ← 1−1/e . 6 λA ← {∅}v∈V . 7 for j ∈ [T ] do 8 9 10
Pick independent uniformly random thresholds ti ∈ (0, 1), for each i ∈ [k]. λjA (v) ← {i ∈ λ(v) : 4 ln m · xi,v ≥ ti }, for every v ∈ V . λA ← λjA ∪ λA .
11 return λA
Theorem 4.1. Algorithm 4 is an O log2 m -approximation algorithm for the Connectivity problem which succeeds with high probability. Proof. In order to show that the algorithm returns a connecting assignment, we first show that with high probability, the subgraph H connects all terminals in each group Ur . It should be remarked that constructing H explicitly is not necessary for the algorithm to work. Nonetheless, we do so for the sake of convenience. We start with the following lemma: Lemma 4.2. With high probability, for every r ∈ [p], H connects all terminals in Ur . Proof. Fix any r ∈ [p] and any S ⊂ V with S ∩ Ur = ̸ ∅ and (V \ S) ∩ Ur = ̸ ∅. Let ℓ ∈ N, such that ℓ ≤ y(δ(S)) < ℓ + 1. We have: Y Y Pr[|δH (S)| = 0] = Pr[Ye = 0] = (1 − pe ) e∈δ(S)
≤
Y e∈δ(S)
e∈δ(S)
X exp {−pe } ≤ exp − min{1, 4 ln m · ye } e∈δ(S)
1 m4ℓ where the last inequality uses the LP constraint y(δ(S)) ≥ 1 for every Ur -separating cut, so P e∈δ(S) ye ≥ ℓ. A cut in G is called an α-minimum cut if its value is less than α times the value of a minimum cut in G. We now make use of the following Karger’s lemma [11, 10]: ≤ exp {−4ℓ ln m} =
Lemma 4.3 (Karger’s lemma). The number of α-minimum cuts in a graph is at most n2α . Observe that by construction of the LP, every Ur -separating fractional cut has value at least 1, so there are at most n2ℓ cuts that are Ur -separating and have fractional value less than ℓ. Fix some r ∈ [p]. Applying the union bound over all all Ur -separating cuts we get: ∞ X Pr ∃ Ur -sep. cut S : |δH (S)| = 0 ≤
X
Pr[|δH (S)| = 0]
S⊂V, S∩Ur ̸=∅ (V \S)∩Ur ̸=∅, y(δ(S))<ℓ+1 ∞ ∞ X X 1 1 1 2ℓ ≤ n · 4ℓ = = 2 2ℓ m −1 m m ℓ=1 ℓ=1 ℓ=1
Thus, applying the union bound over all groups r ∈ [p], no Ur -separating cut is empty in H for any r ∈ [p] with probability at least 1 − m2p−1 . Since p ≤ n ≤ m + 1, we get that with high probability, for every r ∈ [p], the subgraph H connects all terminals in Ur . 10
Having shown that the subgraph H connects all terminals in each group Ur , we now wish to show that the assignment λA returned by the algorithm covers all of the edges of H almost surely. Let j be an index of some iteration of the for loop. Let Hj be the subgraph of H that is not covered by λA at the beginning of the j-th iteration of the for loop. We wish to show, that in expectation, the solution λA produced in the j-th iteration of the for loop, λjA , covers a significant fraction of the edges in Hj . We have the following lemma: h i Lemma 4.4. We have E cov λjA , Hj ≥ (1 − 1/e) · E [|E(Hj )|]. Proof. Consider any edge uv ∈ E(G). Observe that E[Yuv ] ≤ 4 ln m · yuv . By definition of the LP we get that: X
min{xi,u , xi,v } ≥ yuv ≥
i∈λ(u)∩λ(v)
E[Yuv ] · 4 ln m
Therefore, the probability that uv is uncovered by λA is at most: Y Pr[λA (u) ∩ λA (v) = ∅] = Pr[ti > 4 ln m · min{xi,u , xi,v }] i∈λ(u)∩λ(v)
Y
=
{1 − 4 ln m · min{xi,u , xi,v }}
i∈λ(u)∩λ(v)
Y
≤
exp {−4 ln m · min{xi,u , xi,v }}
i∈λ(u)∩λ(v)
X = exp −4 ln m · min{xi,u , xi,v } i∈λ(u)∩λ(v) E[Yuv ] ≤ exp −4 ln m · = exp {−E[Yuv ]} 4 ln m Thus, we have Pr[λA (u) ∩ λA (v) = ̸ ∅] ≥ 1 − exp {−E[Yuv ]}. By summing up over all edges in Hj we lower bound the expected number of edges covered by λjA as follows: i h X E cov λjA , Hj = Pr[λA (u) ∩ λA (v) ̸= ∅] uv∈E(Hj )
≥
X
{1 − exp {−E[Yuv ]}}
uv∈E(Hj )
≥ (1 − 1/e) ·
X
E[Yuv ] ≥ (1 − 1/e) · E [|E(Hj )|]
uv∈E(Hj )
where the second inequality is obtained using the fact that 1 − ex ≤ (1 − 1/e) · x, for x ∈ [0, 1] and the last inequality is obtained by linearity of expectation. Let I be the random variable denoting the number of iterations needed to cover all edges of H, i.e., the smallest j such that cov(λA , H) = E(H) after j iterations (assume that the number of iterations might be larger then T ). We show that with high probability I ≤ T , so the algorithm returns a feasible solution. 1 Lemma 4.5. Pr [I > T ] = O m . Proof. Let α = 1 − 1/e. By definition, |E(Hj+1 )| = |E(Hj )| − cov λjA , Hj . By linearity of expectation and the previous lemma, E [|E(Hj+1 )|] ≤ (1 − α) · E [|E(Hj )|]. Unfolding the 11
recurrence gives E [|E(Hj )|] ≤ me−α(j−1) . By Markov’s inequality, Pr{|E(Hj )| ≥ 1} ≤ me−α(j−1) . 2 ln m Since T = 1−1/e = 2 lnα m , setting j = T gives: Pr[I > T ] = Pr{|E(HT )| ≥ 1} ≤ me
−α(T −1)
−2 ln m+α
≤ me
1 =O m
.
since eα = O(1). It remains to show that the cost of the solution returned by the algorithm is at most 2 O log m · OPT. We have with the following lemma: Lemma 4.6. With high probability, for every vertex v ∈ V (G) and every iteration j ∈ [T ], j cost v, λA ≤ 12 ln m · OPT. Proof. Fix a vertex v ∈ V and an iteration j ∈ [T ]. If v is cheap, then its overall cost is at P most 1 ≤ 2 · OPT regardless of activated interfaces. Thus, assume v to be expensive, j so i∈λ(v) c(i, v) · xi,v ≥ 1. By Xv,i denote the indicator that interface i is chosen at v in P j j j iteration j. Then, cost v, λA = i∈λ(v) c(i, v) · Xv,i . We have E[Xv,i ] = 4 ln m · xi,v , hence P E[cost v, λjA ] = 4 ln m · i∈λ(v) c(i, v) · xi,v . Applying the Chernoff bound with δ = 2 gives: h i e2 E[cost(v,λjA )] j 1 j j Pr cost v, λA ≥ 3 · E[cost v, λA ] ≤ ≤ e−E[cost(v,λA )] ≤ 4 , 27 m P where the last inequality uses E[cost v, λjA ] = 4 ln m · i∈λ(v) c(i, v) · xi,v ≥ 4 ln m. Hence P cost v, λjA ≤ 12 ln m · i∈λ(v) c(i, v) · xi,v ≤ 12 ln m · OPT with probability at least 1 − m14 . 2 ln m Applying the union bound over all n ≤ m + 1 vertices and all T ≤ 1−1/e iterations, the above
≥ 1 − m12 for holds simultaneously for all v ∈ V and j ∈ [T ] with probability at least 1 − T ·(m+1) m4 large values of m. Consequently, summing up over all T iterations, with high probability: cost(λA ) ≤
T X j=1
n o 24 ln2 m ≤ T · 12 ln m · OPT = cost v, λjA · OPT 1 − 1/e v∈V (G) max
Combining the above lemmas gives the desired result.
5
Conclusion
In this work, we have provided the first polylogarithmic approximation algorithms for the Connectivity problem, which is a fundamental problem in covering multi-interface networks. We have also given an O(log m)-approximation algorithm for the Coverage problem, which is almost tight since the problem is NP-hard to approximate within a factor of o(log ∆), even if the input is a star and all costs are uniform [7]. This inapproximability carries on also for the Connectivity problem, since on stars, the Connectivity problem with one terminal set U1 = V is equivalent to the Coverage problem. The remaining question is to close the gap between the O log2 m -approximation algorithm for the Connectivity problem and the 2 O(log m) inapproximability. We conjecture that indeed O log m might be best possible, since the problem shares a lot of similarities with the Group Steiner Tree which cannot be approximated better [9].
12
References [1] Alessandro Aloisio. Min-max coverage in multi-interface networks: pathwidth. In International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, pages 221–232. Springer, 2024. [2] Alessandro Aloisio, Alfredo Navarra, and Leonardo Mostarda. Energy consumption balancing in multi-interface networks. Journal of Ambient Intelligence and Humanized Computing, 11(8):3209–3219, 2020. [3] Haris Angelidakis. Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings. ArXiv, abs/1807.09389, 2018. URL: https://api. semanticscholar.org/CorpusID:51718679. [4] Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, and Evi Papaioannou. Energy-efficient communication in multi-interface wireless networks. Theory of Computing Systems, 52(2):285–296, 2013. [5] Cristina Bazgan, Morgan Chopin, André Nichterlein, and Camille Richer. On the computational complexity of covering multi-interface networks. In WALCOM: Algorithms and Computation, Lecture Notes in Computer Science, pages 232–246. Springer Nature Singapore, 2026. doi:10.1007/978-981-95-7127-7_16. [6] Mauro Caporuscio, Damien Charlet, Valerie Issarny, and Alfredo Navarra. Energetic performance of service-oriented multi-radio networks: issues and perspectives. In Proceedings of the 6th International Workshop on Software and Performance, pages 42–45, 2007. [7] Gianlorenzo D’Angelo, Gabriele Di Stefano, and Alfredo Navarra. Minimize the maximum duty in multi-interface networks. Algorithmica, 63(1-2):274–295, 2012. URL: https://doi. org/10.1007/s00453-011-9531-4, doi:10.1007/S00453-011-9531-4. [8] Gianlorenzo D’Angelo, Gabriele Di Stefano, and Alfredo Navarra. Flow problems in multiinterface networks. IEEE Transactions on Computers, 63:361–374, 2014. doi:10.1109/TC. 2012.214. [9] Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03, page 585–594, New York, NY, USA, 2003. Association for Computing Machinery. doi:10.1145/ 780542.780628. [10] David R. Karger. Random sampling in cut, flow, and network design problems. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’94, page 648–657, New York, NY, USA, 1994. Association for Computing Machinery. doi:10.1145/195058.195422. [11] David R. Karger. Minimum cuts in near-linear time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 56–63, New York, NY, USA, 1996. Association for Computing Machinery. doi:10.1145/237814.237829. [12] Ralf Klasing, Adrian Kosowski, and Alfredo Navarra. Cost minimization in wireless networks with a bounded and unbounded number of interfaces. Networks, 53(3):266–275, 2009. doi:10.1002/net.20266. [13] Adrian Kosowski, Alfredo Navarra, Dariusz Pajak, and Cristina M. Pinotti. Maximum matching in multi-interface networks. Theoretical Computer Science, 507:52–60, 2013. doi:10.1016/j.tcs.2013.01.018. 13
[14] Adrian Kosowski, Alfredo Navarra, and Cristina M. Pinotti. Exploiting multi-interface networks: Connectivity and cheapest paths. Wireless Networks, 16(4):1063–1073, 2010. doi:10.1007/s11276-009-0188-8. [15] Vijay V. Vazirani. Approximation Algorithms. Springer, Berlin, Heidelberg, 2001. doi: 10.1007/978-3-662-04565-7.
A
Weighted Chernoff Bound Derivation
Theorem A.1 ((Weighted) Chernoff bound). Let X1 , X2 , . . . , Xn be independent random variables taking values in [0, 1], let w1 , wP 2 , . . . , wn be non-negative weights, such that for every i ∈ [n] we have that wi ∈ [0, 1]. Let X = ni=1 wi · Xi and let µ = E[X]. Then for every δ1 > 0 and δ2 ∈ (0, 1) we have that: µ µ e δ1 e−δ2 Pr(X ≥ (1 + δ1 ) · µ) ≤ Pr(X ≤ (1 − δ2 ) · µ) ≤ . (1 + δ1 )1+δ1 (1 − δ2 )1−δ2 Proof. We first prove the upper-tail bound for δ1 > 0. For any λ > 0, Markov’s inequality gives: E eλX λX λ·(1+δ1 )·µ Pr(X ≥ (1 + δ1 ) · µ) = Pr e ≥ e ≤ λ·(1+δ )·µ . 1 e λ·X Q By independence, we have E e = ni=1 E eλ·wi ·Xi . Fix i ∈ [n]. Since wi · Xi ∈ [0, 1], by convexity of y 7→ eλ·y on [0, 1], for every y ∈ [0, 1], eλ·y ≤ (1 − y) · e0 + y · eλ = 1 + eλ − 1 · y. Substituting y = wi · Xi , taking expectation, and using 1 + t ≤ et , we obtain: h i E eλ·wi ·Xi ≤ 1 + eλ − 1 · wi · E[Xi ] ≤ exp eλ − 1 · wi · E[Xi ] . Hence: ! n h i X wi · E[Xi ] = exp eλ − 1 · µ . E eλX ≤ exp eλ − 1 · i=1
Therefore, Pr(X ≥ (1 + δ1 ) · µ) ≤ exp µ · eλ − 1 − λ · (1 + δ1 ) . The function f (λ) = eλ − 1 − λ · (1 + δ1 ) is minimized at λ = ln(1 + δ1 ), and so: !µ e δ1 Pr(X ≥ (1 + δ1 ) · µ) ≤ exp(−µ · ((1 + δ1 ) · ln(1 + δ1 ) − δ1 )) = . (1 + δ1 )1+δ1 Now let δ2 ∈ (0, 1). For any t > 0, again by Markov’s inequality: E e−t·X −tX −t·(1−δ2 )·µ Pr(X ≤ (1 − δ2 ) · µ) = Pr e ≥e ≤ −t·(1−δ )·µ . 2 e −t·X Applying the same mgf estimate with λ = −t < 0 yields E e ≤ exp e−t − 1 · µ , so: Pr(X ≤ (1 − δ2 ) · µ) ≤ exp µ · e−t − 1 + t · (1 − δ2 ) . The right-hand side is minimized at t = − ln(1 − δ2 ), which gives: Pr(X ≤ (1 − δ2 ) · µ) ≤ exp(−µ · (δ2 + (1 − δ2 ) · ln(1 − δ2 ))) =
14
e−δ2 (1 − δ2 )1−δ2
!µ .