An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
复制标题
DOI：
10.1007/s40314-022-01984-2
复制
发表时间：
2022-08
影响因子：
2.6
通讯作者：
Jiaxuan Zhang;Suogang Gao;Bo Hou;Wen Liu
中科院分区：
文献类型：
--
作者：
Jiaxuan Zhang;Suogang Gao;Bo Hou;Wen Liu
在这篇文章中，我们考虑了具有子模惩罚的群体获奖Steiner树问题(GPCST-SP问题)。在这个问题中，我们得到了一个无向连通图，它具有预先指定的根和Vwith的划分。假设是一个边值函数，是一个子模惩罚函数，其中是一组非负实数。对于一个组，如果树至少包含该组的一个顶点，我们称它为树所跨。GPCST-SP问题的目标是找到一棵有根的树，使树中边的代价加上包含不被树生成的这些组的子集的惩罚代价最小。我们的主要结果是该问题的一个2i-近似算法，其中。
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 graphwith a pre-specified rootrand a partitionofVwith. Assumeis an edge cost function andis a submodular penalty function, whereis the set of nonnegative real numbers. For a group, 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 anr-rooted tree that minimizes the costs of the edges in the tree plus the penalty cost of the subcollectioncontaining these groups not spanned by the tree. Our main result is a 2I-approximation algorithm for the problem, where.