Approximation Algorithms for Connected Maximum Coverage

The Connected Budgeted maximum Coverage problem (CBC) is a combinatorial optimization problem that finds applications in path planning, wireless sensor networks, logistics, and bioinformatics. In CBC, we are given a collection of subsets S, defined over a ground set 𝑋 , and an undirected graph 𝐺 = (𝑉 , 𝐸), where each node is associated with a set of S. Each set in S has a different cost and each element of 𝑋 gives a different prize. The goal is to find a subcollection S ′ ⊆ S such that S ′ induces a connected subgraph in 𝐺, the total cost of the sets in S ′ does not exceed a budget 𝐵, and the total prize of the elements covered by S ′ (i.e., 𝑆 ∈ S ′ 𝑆) is maximized. The Directed rooted Connected Budgeted maximum Coverage problem (DCBC) is a generalization of CBC where the underlying graph 𝐺 is directed and in the subgraph induced by S ′ in 𝐺 there must be a path from a specific node called root to any other node. These 𝑁 𝑃-hard problems have been widely studied from the approximation point of view. Still, the current best algorithms achieve approximation ratios that are linear in the size of the underlying graph or depend on 𝐵. In this paper, we provide two algorithms for CBC and DCBC that guarantee approximation ratios of 𝑂 log (|𝑉 |+|𝑋 |) log |𝑋 | 𝜖 2 and 𝑂 √ |𝑉 | log 2 |𝑋 | 𝜖 2 , respectively, at the cost of a violation in the budget constraint of a factor 1 + 𝜖, where 𝜖 ∈ (0, 1]. We also improve the approximation factor for the directed budgeted rooted out-tree maximization problem, a particular case of DCBC where the prize function is additive, from 𝑂 1 𝜖 2 |𝑉 | 2/3 log |𝑉 | to 𝑂 1 𝜖 2 |𝑉 | 1/2 log 2 |𝑉 | , for any 𝜖 ∈ (0, 1].