Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.07725 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909574014959616 |
|---|---|
| author | D'Angelo, Gianlorenzo Delfaraz, Esmaeil |
| author_facet | D'Angelo, Gianlorenzo Delfaraz, Esmaeil |
| contents | In the Connected Budgeted maximum Coverage problem (CBC), we are given a collection of subsets $\mathcal{S}$, defined over a ground set $X$, and an undirected graph $G=(V,E)$, where each node is associated with a set of $\mathcal{S}$. Each set in $\mathcal{S}$ has a different cost and each element of $X$ gives a different prize. The goal is to find a subcollection $\mathcal{S}'\subseteq \mathcal{S}$ such that $\mathcal{S}'$ induces a connected subgraph in $G$, the total cost of the sets in $\mathcal{S}'$ does not exceed a budget $B$, and the total prize of the elements covered by $\mathcal{S}'$ is maximized. The Directed rooted Connected Budgeted maximum Coverage problem (DCBC) is a generalization of CBC where the underlying graph $G$ is directed and in the subgraph induced by $\mathcal{S}'$ in $G$ must be an out-tree rooted at a given node.
The current best algorithms achieve approximation ratios that are linear in the size of $G$ or depend on $B$. In this paper, we provide two algorithms for CBC and DCBC that guarantee approximation ratios of $O\left(\frac{\log^2|X|}{ε^2}\right)$ and $O\left(\frac{\sqrt{|V|}\log^2|X|}{ε^2}\right)$, resp., with a budget violation of a factor $1+ε$, where $ε\in (0,1]$.
Our algorithms imply improved approximation factors of other related problems. For the particular case of DCBC where the prize function is additive, we improve from $O\left(\frac{1}{ε^2}|V|^{2/3}\log|V|\right)$ to $O\left(\frac{1}{ε^2}|V|^{1/2}\log^2|V|\right)$. For the minimum connected set cover, a minimization version of CBC, and its directed variant, we obtain approximation factors of $O(\log^3|X|)$ and $O(\sqrt{|V|}\log^3|X|)$, resp. For the Node-Weighted Group Steiner Tree and and its directed variant, we obtain approximation factors of $O(\log^3k)$ and $O(\sqrt{|V|}\log^3k)$, resp., where $k$ is the number of groups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_07725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree D'Angelo, Gianlorenzo Delfaraz, Esmaeil Data Structures and Algorithms In the Connected Budgeted maximum Coverage problem (CBC), we are given a collection of subsets $\mathcal{S}$, defined over a ground set $X$, and an undirected graph $G=(V,E)$, where each node is associated with a set of $\mathcal{S}$. Each set in $\mathcal{S}$ has a different cost and each element of $X$ gives a different prize. The goal is to find a subcollection $\mathcal{S}'\subseteq \mathcal{S}$ such that $\mathcal{S}'$ induces a connected subgraph in $G$, the total cost of the sets in $\mathcal{S}'$ does not exceed a budget $B$, and the total prize of the elements covered by $\mathcal{S}'$ is maximized. The Directed rooted Connected Budgeted maximum Coverage problem (DCBC) is a generalization of CBC where the underlying graph $G$ is directed and in the subgraph induced by $\mathcal{S}'$ in $G$ must be an out-tree rooted at a given node. The current best algorithms achieve approximation ratios that are linear in the size of $G$ or depend on $B$. In this paper, we provide two algorithms for CBC and DCBC that guarantee approximation ratios of $O\left(\frac{\log^2|X|}{ε^2}\right)$ and $O\left(\frac{\sqrt{|V|}\log^2|X|}{ε^2}\right)$, resp., with a budget violation of a factor $1+ε$, where $ε\in (0,1]$. Our algorithms imply improved approximation factors of other related problems. For the particular case of DCBC where the prize function is additive, we improve from $O\left(\frac{1}{ε^2}|V|^{2/3}\log|V|\right)$ to $O\left(\frac{1}{ε^2}|V|^{1/2}\log^2|V|\right)$. For the minimum connected set cover, a minimization version of CBC, and its directed variant, we obtain approximation factors of $O(\log^3|X|)$ and $O(\sqrt{|V|}\log^3|X|)$, resp. For the Node-Weighted Group Steiner Tree and and its directed variant, we obtain approximation factors of $O(\log^3k)$ and $O(\sqrt{|V|}\log^3k)$, resp., where $k$ is the number of groups. |
| title | Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.07725 |