Abstract
We consider a variant of the prize collecting Steiner tree problem in which we are given a directed graph D = (V,A), a monotone submodular prize function p:2^V → ℝ^+ ∪ {0}, a cost function c:V → ℤ^+, a root vertex r ∈ V, and a budget B. The aim is to find an outsubtree T of D rooted at r that costs at most B and maximizes the prize function. We call this problem Directed Rooted Submodular Tree (DRST).
For the case of undirected graphs and additive prize functions, Moss and Rabani [SIAM J. Comput. 2007] gave an algorithm that guarantees an O(logV)approximation factor if a violation by a factor 2 of the budget constraint is allowed. Bateni et al. [SIAM J. Comput. 2018] improved the budget violation factor to 1+ε at the cost of an additional approximation factor of O(1/ε²), for any ε ∈ (0,1]. For directed graphs, Ghuge and Nagarajan [SODA 2020] gave an optimal quasipolynomial time O({log n'}/{log log n'})approximation algorithm, where n' is the number of vertices in an optimal solution, for the case in which the costs are associated to the edges.
In this paper, we give a polynomial time algorithm for DRST that guarantees an approximation factor of O(√B/ε³) at the cost of a budget violation of a factor 1+ε, for any ε ∈ (0,1]. The same result holds for the edgecost case, to the best of our knowledge this is the first polynomial time approximation algorithm for this case. We further show that the unrooted version of DRST can be approximated to a factor of O(√B) without budget violation, which is an improvement over the factor O(Δ √B) given in [Kuo et al. IEEE/ACM Trans. Netw. 2015] for the undirected and unrooted case, where Δ is the maximum degree of the graph. Finally, we provide some new/improved approximation bounds for several related problems, including the additiveprize version of DRST, the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.
BibTeX  Entry
@InProceedings{dangelo_et_al:LIPIcs.ISAAC.2022.9,
author = {D'Angelo, Gianlorenzo and Delfaraz, Esmaeil and Gilbert, Hugo},
title = {{Budgeted OutTree Maximization with Submodular Prizes}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {9:19:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17294},
URN = {urn:nbn:de:0030drops172945},
doi = {10.4230/LIPIcs.ISAAC.2022.9},
annote = {Keywords: Prize Collecting Steiner Tree, Directed graphs, Approximation Algorithms, Budgeted Problem}
}
Keywords: 

Prize Collecting Steiner Tree, Directed graphs, Approximation Algorithms, Budgeted Problem 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 