AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
PDF (829.3 KB)
Cite
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
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 (PC $k$ST) 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 PC $k$ST 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 PC $k$ST. This algorithm uses the approximation algorithms for the prize-collecting Steiner tree (PCST) problem and the $k$-Steiner tree ( $k$ST) problem as subroutines. Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to $5$.

## 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.
[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.
[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.
[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.
[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.
[6]
L. Han, D. Xu, D. Du, and D. Zhang, An approximation algorithm for the uniform capacitated k-means problem, Journal of Combinatorial Optimization, .
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
Tsinghua Science and Technology
Pages 785-792
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

857

Views

83

0

Crossref

0

Web of Science

0

Scopus

1

CSCD

Altmetrics