Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Blood Leukocyte Object Detection According to Model Parameter-Transfer and Deformable Convolution Read chapter Read first chapter

2021 | OriginalPaper | Chapter

The Prize-Collecting k-Steiner Tree Problem

Authors : Lu Han, Changjun Wang, Dachuan Xu, Dongmei Zhang

Published in: Parallel and Distributed Computing, Applications and Technologies

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we study the prize-collecting k-Steiner tree problem (PC k-ST), which is an interesting generalization of both the k-Steiner tree problem (k-ST) and the prize-collecting Steiner tree problem (PCST). In the PC k-ST, we are given an undirected connected graph \(G =(V, E)\), a subset \(R \subseteq V\) called terminals, a root vertex \(r \in V\) and an integer k. Every edge has a non-negative edge cost and every vertex has a non-negative penalty cost. We wish to find an r-rooted tree F that spans at least k vertices in R so as to minimize the total edge costs of F as well as the penalty costs of the vertices not in F. As our main contribution, we propose two approximation algorithms for the PC k-ST with ratios of 5.9672 and 5. The first algorithm is based on an observation of the solutions for the k-ST and the PCST, and the second one is based on the technique of primal-dual.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Streaming Model for Monotone Lattice Submodular Maximization with a Cardinality Constraint
next chapter Optimal Algorithm of Isolated Toughness for Interval Graphs
Literature
1.
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)MathSciNetCrossRef
2.
Arora, S., Karakostas, G.: A \(2+\varepsilon \) approximation algorithm for the \(k\)-MST problem. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 754–759 (2000)
3.
Arya, S., Ramesh, H.A.: \(2.5\)-factor approximation algorithm for the \(k\)-MST problem. Inf. Process. Lett. 65, 117–118 (1998)MathSciNetCrossRef
4.
Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: Improved approximation guarantees for minimum-weight \(k\)-trees and prize-collecting salesmen. SIAM J. Comput. 28, 254–262 (1999)MathSciNetCrossRef
5.
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)MathSciNetCrossRef
6.
Blum, A., Ravi, R., Vempala, S.: A constant-factor approximation algorithm for the \(k\)-MST problem. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 442–448 (1996)
7.
Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation. Math. Program. 100, 411–421 (2004)MathSciNetCrossRef
8.
Fischetti, M., Hamacher, H.W., Jørnsten, K., Maffioli, F.: Weighted \(k\)-cardinality trees: complexity and polyhedral structure. Networks 24, 11–21 (1994)
9.
Garg, N.: A \(3\)-approximation for the minimum tree spanning \(k\) vertices. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 302–309 (1996)
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.
Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296–317 (1995)MathSciNetCrossRef
12.
Han, L., Xu, D., Du, D., Wu, C.: A \(5\)-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem. Optim. Lett. 13, 573–585 (2019)MathSciNetCrossRef
13.
Han, L., Xu, D., Du, D., Wu, C.: A primal-dual algorithm for the generalized prize-collecting Steiner forest problem. J. Oper. Res. Soc. China 5, 219–231 (2017)MathSciNetCrossRef
14.
Matsuda, Y., Takahashi, S.: A \(4\)-approximation algorithm for \(k\)-prize collecting Steiner tree problems. Optim. Lett. 13, 341–348 (2019)MathSciNetCrossRef
15.
Rajagopalan, S., Vazirani, V.V.: Logarithmic approximation of minimum weight \(k\) trees. Unpublished manuscript (1995)
16.
Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees short or small. SIAM J. Discrete Math. 9, 178–200 (1996)MathSciNetCrossRef
17.
Xu, Y., Xu, D., Du, D., Wu, C.: Improved approximation algorithm for universal facility location problem with linear penalties. Theor. Comput. Sci. 774, 143–151 (2019)MathSciNetCrossRef
18.
Xu, Y., Xu, D., Du, D., Zhang, D.: Approximation algorithm for squared metric facility location problem with non uniform capacities. Discrete Appl. Math. 264, 208–217 (2019)MathSciNetCrossRef
Metadata
Title
The Prize-Collecting k-Steiner Tree Problem
Authors
Lu Han
Changjun Wang
Dachuan Xu
Dongmei Zhang
Copyright Year
2021
Book
Parallel and Distributed Computing, Applications and Technologies

Print ISBN: 978-3-030-69243-8

Electronic ISBN: 978-3-030-69244-5

Copyright Year: 2021

DOI
https://doi.org/10.1007/978-3-030-69244-5_33

Premium Partner

    Image Credits