Journal
COMPUTATIONAL & APPLIED MATHEMATICS
Volume 41, Issue 6, Pages -Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s40314-022-01984-2
Keywords
Group prize-collecting Steiner tree problem; Submodular function; Approximation algorithm
Categories
Funding
- NSF of China [11971146]
- NSF of Hebei Province of China [A2019205089, A2019205092]
- Hebei Province Foundation for Returnees [CL201714]
- Overseas Expertise Introduction Program of Hebei Auspices [25305008]
- Graduate Innovation Grant Program of Hebei Normal University [CXZZSS2022052]
Ask authors/readers for more resources
This paper considers the group prize-collecting Steiner tree problem with submodular penalties. The goal of the problem is to find an r-rooted tree that minimizes the costs of the edges in the tree plus the penalty cost of the subcollection not spanned by the tree. The main result is a 2I-approximation algorithm for the problem.
In this paper, we consider the group prize-collecting Steiner tree problem with submodular penalties (GPCST-SP problem). In this problem, we are given an undirected connected graph G = (V, E) with a pre-specified root r and a partition V = {V-0, V-1, ..., V-k} of V with r is an element of V-0. Assume c : E -> R+ is an edge cost function and p : 2(V) -> R+ is a submodular penalty function, where R+ is the set of nonnegative real numbers. For a group V-i is an element of V, we say it is spanned by a tree if the tree contains at least one vertex of that group. The goal of the GPCST-SP problem is to find an r-rooted tree that minimizes the costs of the edges in the tree plus the penalty cost of the subcollection S containing these groups not spanned by the tree. Our main result is a 2I-approximation algorithm for the problem, where I = max{vertical bar V-i vertical bar vertical bar i = 0, 1, 2, ..., k}.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available