Skip to main content
SpringerLink
Log in

A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

Abstract

In this paper, we consider the generalized prize-collecting Steiner forest problem, extending the prize-collecting Steiner forest problem. In this problem, we are given a connected graph \(G = (V, E)\) and a set of vertex sets \({\mathcal {V}} = \{V_1, V_2,\cdots , V_{l}\}\). Every edge in E has a nonnegative cost, and every vertex set in \({\mathcal {V}}\) has a nonnegative penalty cost. For a given edge set \(F\subseteq E\), vertex set \(V_i\in {\mathcal {V}}\) is said to be connected by edge set F if \(V_i\) is in a connected component of the F-spanned subgraph. The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is minimized. Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: Foundations of Computer Science. Proceedings of the 38th Annual Symposium on IEEE, pp. 542–547 (1997)

  2. Salman, F.S., Cheriyan, J., Ravi, R., Subramanian, S.: Approximating the single-sink link-installation problem in network design. SIAM J. Optim. 11, 595–610 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.P.: A note on the prize collecting traveling salesman problem. Math. Program. 59, 413–420 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  4. Hajiaghayi, M.T., Jain, K.: The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, Society for Industrial and Applied Mathematics, pp. 631–640 (2006)

  5. Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1–29 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  6. Karpinski, M., Zelikovsky, A.: New approximation algorithms for the Steiner tree problems. J. Comb. Optim. 1, 47–65 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  7. Prömel, H.J., Steger, A.: A new approximation algorithm for the Steiner tree problem with performance ratio 5/3. J. Algorithms 36, 89–101 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  8. Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19, 122–134 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  9. Zelikovsky, A.: An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 463–470 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  10. Byrka, J., Grandoni, F., Rothvoss, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60, 6:1–6:33 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  11. 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 

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

    Article  MathSciNet  MATH  Google Scholar 

  13. Sharma, Y., Swamy, C., Williamson, D.P.: Approximation algorithms for prize collecting forest problems with submodular penalty functions. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp. 1275–1284 (2007)

Download references

Author information

Authors and Affiliations

  1. Department of Information and Operations Research, Beijing University of Technology, Beijing, 100124, China

    Lu Han & Da-Chuan Xu

  2. Faculty of Business Administration, University of New Brunswick, Fredericton, NB, E3B 5A3, Canada

    Dong-Lei Du

  3. College of Science, Tianjin University of Technology, Tianjin, 300384, China

    Chen-Chen Wu

Authors
  1. Lu Han
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Da-Chuan Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dong-Lei Du
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Chen-Chen Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Da-Chuan Xu.

Additional information

This paper is dedicated to Professor Lian-Sheng Zhang in celebration of his 80th birthday.

D.-C. Xu is supported by the National Natural Science Foundation of China (No. 11371001) and Collaborative Innovation Center on Beijing Society-Building and Social Governance. D.-L. Du is supported by the Natural Sciences and Engineering Research Council of Canada (No. 06446). C.-C. Wu is supported by the National Natural Science Foundation of China (No. 11501412).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Han, L., Xu, DC., Du, DL. et al. A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem. J. Oper. Res. Soc. China 5, 219–231 (2017). https://doi.org/10.1007/s40305-017-0164-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-017-0164-4

Keywords

Mathematics Subject Classification

Search

Navigation