## Abstract

In this paper, we study the prize-collecting

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'}}

Powered by AMiner. Clicking this button will take you away from SciOpen.

About Us

Discover the SciOpen Platform and Achieve Your Research Goals with Ease.

Show Outline

Outline

Outline

Open Access

In this paper, we study the prize-collecting

[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
Metrics & Citations

Pages 785-792

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

857

Views

83

Downloads

0

Crossref

0

Web of Science

0

Scopus

1

CSCD

Altmetrics

Received: 10 May 2021

Revised: 17 June 2021

Accepted: 17 July 2021

Published:
17 March 2022

© The author(s) 2022.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).