Polylogarithmic Approximation for Covering and Connecting Multi-Interface Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910200172118016 |
|---|---|
| author | Szyfelbein, Michał Richer, Camille |
| author_facet | Szyfelbein, Michał Richer, Camille |
| contents | We study problems related to connecting multi-interface networks of wireless devices. These problems are 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 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 minimize 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 ILPs 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\cdot\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(\log^2 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_06899 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Polylogarithmic Approximation for Covering and Connecting Multi-Interface Networks Szyfelbein, Michał Richer, Camille Data Structures and Algorithms Networking and Internet Architecture We study problems related to connecting multi-interface networks of wireless devices. These problems are 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 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 minimize 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 ILPs 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\cdot\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(\log^2 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. |
| title | Polylogarithmic Approximation for Covering and Connecting Multi-Interface Networks |
| topic | Data Structures and Algorithms Networking and Internet Architecture |
| url | https://arxiv.org/abs/2605.06899 |