Open Access
Issue
Published:
*17 March 2022*

Cite this article:

Han L, Wang C, Xu D, et al.
Algorithms for the Prize-Collecting
Download citation

447

Views

56

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

In this paper, we study the prize-collecting

menu

Abstract

Full text

Outline

About this article

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.

Publication history

Copyright

Acknowledgements

Rights and permissions

Received: 10 May 2021

Revised: 17 June 2021

Accepted: 17 July 2021

Published:
17 March 2022

Issue date: October 2022

© The author(s) 2022.

This paper was supported by the National Natural Science Foundation of China (Nos. 12001523, 11971046, 12131003, and 11871081), the Scientific Research Project of Beijing Municipal Education Commission (No. KM201910005012), and Beijing Natural Science Foundation Project (No. Z200002).

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/).