A 5-approximation algorithm for the k-prize-collecting Steiner tree problem

作者：Han, Lu; Xu, Dachuan^*; Du, Donglei; Wu, Chenchen

来源：Optimization Letters, 2019, 13(3): 573-585.

DOI：10.1007/s11590-017-1135-8

• Prize-collecting Steiner tree
• k-MST
• Approximation algorithm
• Primal-dual
• Lagrangean relaxation

In this paper, we consider the k-prize-collecting Steiner tree problem (k-PCST), extending both the prize-collecting Steiner tree problem (PCST) and the k-minimum spanning tree problem (k-MST). In this problem, we are given a connected graph G=(V,E), a root vertex r and an integer k. Every edge in E has a nonnegative cost. Every vertex in V has a nonnegative penalty cost. We want to find an r-rooted tree F that spans at least k vertices such that the total cost, including the edge cost of the tree F and the penalty cost of the vertices not spanned by F, is minimized. Our main contribution is to present a 5-approximation algorithm for the k-PCST via the methods of primal-dual and Lagrangean relaxation.

• 出版日期2019-4
• 单位北京工业大学; 天津理工大学