A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929315795435520 |
|---|---|
| author | Rockel-Wolff, Benjamin |
| author_facet | Rockel-Wolff, Benjamin |
| contents | The capacitated tree cover problem with edge loads is a variant of the tree cover problem, where we are given facility opening costs, edge costs and loads, as well as vertex loads. We try to find a tree cover of minimum cost such that the total edge and vertex load of each tree does not exceed a given bound. We present an $\mathcal{O}(m\log n)$ time 3-approximation algorithm for this problem.
This is achieved by starting with a certain LP formulation. We give a combinatorial algorithm that solves the LP optimally in time $\mathcal{O}(m\log n)$. Then, we show that a linear time rounding and splitting technique leads to an integral solution that costs at most 3 times as much as the LP solution. Finally, we prove that the integrality gap of the LP is $3$, which shows that we can not improve the rounding step in general. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10638 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads Rockel-Wolff, Benjamin Data Structures and Algorithms Discrete Mathematics Combinatorics 68R10, 68W25, 05C05, 90C27 F.2.2; G.2.1; G.2.2 The capacitated tree cover problem with edge loads is a variant of the tree cover problem, where we are given facility opening costs, edge costs and loads, as well as vertex loads. We try to find a tree cover of minimum cost such that the total edge and vertex load of each tree does not exceed a given bound. We present an $\mathcal{O}(m\log n)$ time 3-approximation algorithm for this problem. This is achieved by starting with a certain LP formulation. We give a combinatorial algorithm that solves the LP optimally in time $\mathcal{O}(m\log n)$. Then, we show that a linear time rounding and splitting technique leads to an integral solution that costs at most 3 times as much as the LP solution. Finally, we prove that the integrality gap of the LP is $3$, which shows that we can not improve the rounding step in general. |
| title | A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 68R10, 68W25, 05C05, 90C27 F.2.2; G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2404.10638 |