AAMAS Conference 2025 Conference Paper
Approximation Algorithms for Connected Maximum Coverage
- Gianlorenzo D'Angelo
- Esmaeil Delfaraz
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 π β |π | log2 |π | π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 log2 |π |, for any π β (0, 1].