Skip to main content
SpringerLink
Log in

A 4-approximation algorithm for k-prize collecting Steiner tree problems

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algorithm employs two 2-approximation algorithms for k-minimum spanning tree problems and prize collecting Steiner tree problems. Also our algorithm framework can be applied to a special case of k-prize collecting traveling salesman problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Korte, B.H., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin (2004)

    MATH  Google Scholar 

  2. Han, L., Xu, D., Du, D., Wu, C.: A 5-approximation algorithm for the k-prize-collecting Steiner tree problem. Optim. Lett. (2017). https://doi.org/10.1007/s11590-017-1135-8

  3. Ravi, R., Sundaram, R., Marathe, M., Rosenkrantz, D., Ravi, S.: Spanning trees short and small. SIAM J. Discrete Math. 9(2), 178–200 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  4. Fischetti, M., Hamacher, H.W., Jörnsten, K., Maffioli, F.: Weighted \(k\)-cardinality trees: complexity and polyhedral structure. Networks 24, 11–21 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  5. Garg, N.: A 3-approximation for the minimum tree spanning \(k\) vertices. In: Proceedings of 37th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 302–309 (1996)

  6. Blum, A., Ravi, R., Vempala, S.: A constant factor approximation for the \(k\)-MST problem. J. Comput. Syst. Sci. 58(1), 101–108 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  7. Arora, S., Karakostas, G.: A \(2+\epsilon \) approximation algorithm for the \(k\)-MST problem. Math. Program. Ser. A 107, 491–504 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  8. Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296–317 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  9. Archer, A., Mohammadhossein, B., Hajiaghayi, M., Karloff, H.: Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40, 309–332 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  10. Garg, N.: Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 396–402 (2005)

  11. Ausiello, G., Bonifaci, V., Leonardi, S., Spaccamela, A.M.: Prize collecting traveling salesman problem and related problems. In: Handbook of Approximation Algorithms and Metaheuristics, Chapter 40. Chapman & Hall/CRC (2007)

  12. Balas, E.: The prize collecting traveling salesman problem. Networks 19, 621–636 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  13. Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: New approximation guarantees for minimum-weight \(k\)-trees and prize-collecting salesmen. SIAM J. Comput. 28(1), 254–262 (1998)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We thank one anonymous reviewer for very valuable feedback. This research was partially supported by the Ministry of Education, Science, Sports and Culture through Grants-in-Aid for Scientific Research (C) 26330025, (B) 15H02972, and through Grants-in-Aid for Young Scientists (B) 26870200.

Author information

Authors and Affiliations

  1. The University of Electro-Communications, Chofu, Japan

    Yusa Matsuda & Satoshi Takahashi

Authors
  1. Yusa Matsuda
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Satoshi Takahashi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Satoshi Takahashi.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Matsuda, Y., Takahashi, S. A 4-approximation algorithm for k-prize collecting Steiner tree problems. Optim Lett 13, 341–348 (2019). https://doi.org/10.1007/s11590-018-1367-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-018-1367-2

Keywords

Search

Navigation