Home Tsinghua Science and Technology Article
PDF (829.3 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

Algorithms for the Prize-Collecting k-Steiner Tree Problem

School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China
School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, China
Show Author Information

Abstract

In this paper, we study the prize-collecting k-Steiner tree (PCkST) problem. We are given a graph G=(V,E) and an integer k. The graph is connected and undirected. A vertex r∈V called root and a subset R⊆V called terminals are also given. A feasible solution for the PCkST is a tree F rooted at r and connecting at least k vertices in R. Excluding a vertex from the tree incurs a penalty cost, and including an edge in the tree incurs an edge cost. We wish to find a feasible solution with minimum total cost. The total cost of a tree F is the sum of the edge costs of the edges in F and the penalty costs of the vertices not in F. We present a simple approximation algorithm with the ratio of 5.9672 for the PCkST. This algorithm uses the approximation algorithms for the prize-collecting Steiner tree (PCST) problem and the k-Steiner tree (kST) problem as subroutines. Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to 5.

Keywords

prize-collectingSteiner treeapproximation algorithm

References

[1]
A. Archer, M. H. Bateni, M. T. Hajiaghayi, and H. Karloff, Improved approximation algorithms for prize-collecting Steiner tree and TSP, SIAM J. Compt. vol. 40, no. 2, pp. 309–332, 2011.
Crossref Google Scholar
[2]
D. Bienstock, M. X. Goemans, D. Simchi-Levi, and D. P. Williamson, A note on the prize collecting traveling salesman problem, Mathematical Programming, vol. 59, nos. 1–3, pp. 413–420, 1993.
Crossref Google Scholar
[3]
F. A. Chudak, T. Roughgarden, and D. P. Williamson, Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation, Mathematical Programming, vol. 100, no. 2, pp. 411–421, 2004.
Crossref Google Scholar
[4]
L. Han, D. Xu, D. Du, and C. Wu, A 5-approximation algorithm for the k-prize-collecting Steiner tree problem, Optimization Letters, vol. 13, no. 3, pp. 573–585, 2019.
Crossref Google Scholar
[5]
L. Han, D. Xu, D. Du, and C. Wu, A primal-dual algorithm for the generalized prize-collecting Steiner forest problem, Journal of the Operations Research Society of China, vol. 5, no. 2, pp. 219–231, 2017.
Crossref Google Scholar
[6]
L. Han, D. Xu, D. Du, and D. Zhang, An approximation algorithm for the uniform capacitated k-means problem, Journal of Combinatorial Optimization, .
Crossref Google Scholar
[7]
L. Han, D. Xu, D. Du, and D. Zhang, A local search approximation algorithm for the uniform capacitated k-facility location problem, Journal of Combinatorial Optimization, vol. 35, no. 2, pp. 409–423, 2018.
Crossref Google Scholar
[8]
L. Han, D. Xu, M. Li, and D. Zhang, Approximation algorithms for the robust facility leasing problem, Optimization Letters, vol. 12, no.3, pp. 625–637, 2018.
Crossref Google Scholar
[9]
L. Han, D. Xu, Y. Xu, and D. Zhang, Approximating the τ-relaxed soft capacitated facility location problem, Journal of Combinatorial Optimization, vol. 40, no.3, pp. 848–860, 2020.
Crossref Google Scholar
[10]
J. Li, A. M. V. V. Sai, X. Cheng, W. Cheng, Z. Tian, and Y. Li, Sampling-based approximate skyline query in sensor equipped IoT networks, Tsinghua Science and Technology, vol. 26, no. 2, pp. 219–229, 2021.
Crossref Google Scholar
[11]
R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz, and S. S. Ravi, Spanning trees short or small, SIAM J. Discrete Math., vol. 9, no. 2, pp. 178–200, 1996.
Crossref Google Scholar
[12]
Y. Xu, R. H. Möhring, D. Xu, Y. Zhang, and Y. Zou, A constant FPT approximation algorithm for hard-capacitated k-means, Optimization and Engineering, vol. 21, no. 3, pp. 709–722, 2020.
Crossref Google Scholar
[13]
Y. Xu, D. Xu, D. Du, and C. Wu, Improved approximation algorithm for universal facility location problem with linear penalties, Theoretical Computer Science, vol. 774, pp. 143–151, 2019.
Crossref Google Scholar
[14]
Y. Xu, D. Xu, D. Du, and C. Wu, Local search algorithm for universal facility location problem with linear penalties, Journal of Global Optimization, vol 67, nos. 1&2, pp. 367–378, 2017.
Crossref Google Scholar
[15]
Y. Xu, D. Xu, D. Du, and D. Zhang, Approximation algorithm for squared metric facility location problem with nonuniform capacities, Discrete Applied Mathematics, vol. 264, pp. 208–217, 2019.
Crossref Google Scholar
[16]
Y. Xu, D. Xu, Y. Zhang, and J. Zou, MpUFLP: Universal facility location problem in the p-th power of metric space, Theoretical Computer Science, vol. 838, pp. 58–67, 2020.
Crossref Google Scholar
[17]
Y. Zhang and H. Zhu, Approximation algorithm for weighted weak vertex cover, Journal of Computer Science and Technology, vol. 19, no. 6, pp. 782–786, 2004.
Crossref Google Scholar
[18]
M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems, SIAM J. Comput., vol. 24, no. 2, pp. 296–317, 1995.
Crossref Google Scholar
[19]
S. Arora and G. Karakostas, A 2 + ε approximation algorithm for the k-MST problem, in Proc. of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 2000, pp. 754–759.
[20]
S. Arya and H. A. Ramesh, A 2.5-factor approximation algorithm for the k-MST problem, Information Processing Letters, vol. 65, no. 3, pp. 117–118, 1998.
Crossref Google Scholar
[21]
B. Awerbuch, Y. Azar, A. Blum, and S. Vempala, New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, SIAM J. Comput., vol. 28, no. 1, pp. 254–262, 1999.
Crossref Google Scholar
[22]
A. Blum, R. Ravi, and S. Vempala, A constant-factor approximation algorithm for the k-MST problem, in Proc. of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA, 1996, pp. 442–448.
Crossref
[23]
M. Fischetti, H. W. Hamacher, K. Jørnsten, and F. Maffioli, Weighted k-cardinality trees: Complexity and polyhedral structure, Networks, vol. 24, no. 1, pp. 11–21, 1994.
Crossref Google Scholar
[24]
N. Garg, A 3-approximation for the minimum tree spanning k vertices, in Proc. of the 37th Annual Symposium on Foundations of Computer Science, Burlington, VT, USA, 1996, pp. 302–309.
[25]
N. Garg, Saving an epsilon: A 2-approximation for the k-MST problem in graphs, in Proc. of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 2005, pp. 396–402.
Crossref
[26]
Y. Matsuda and S. Takahashi, A 4-approximation algorithm for k-prize collecting Steiner tree problems, Optimization Letters, vol. 13, no. 2, pp. 341–348, 2019.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 27 Issue 5,
October 2022
Pages 785-792
DOI: 10.26599/TST.2021.9010053
Cite this article:
Han L, Wang C, Xu D, et al. Algorithms for the Prize-Collecting k-Steiner Tree Problem. Tsinghua Science and Technology, 2022, 27(5): 785-792. https://doi.org/10.26599/TST.2021.9010053
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return