Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem

Jian Sun; Haiyun Sheng; Yuefang Sun; Donglei Du; Xiaoyan Zhang

doi:10.3934/jimo.2021116

Article Contents

2022, Volume 18, Issue 5: 3351-3363. Doi: 10.3934/jimo.2021116

This issue Previous Article Filled function method to optimize supply chain transportation costs Next Article Collection decisions and coordination in a closed-loop supply chain under recovery price and service competition

Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem

1.
Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, China
2.
School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Jiangsu 210023, China
3.
School of Mathematics and Statistics, Ningbo University, Zhejiang 315211, China
4.
Faculty of Management, University of New Brunswick, New Brunswick, E3B 5A3, Canada

^* Corresponding author: Xiaoyan Zhang, zhangxiaoyannjnu@126.com
^* Corresponding author: Xiaoyan Zhang, zhangxiaoyannjnu@126.com

Received: October 31, 2020

Revised: March 31, 2021

Early access: July 2021

Published: November 2022

A preliminary version appeared in the Proceedings of the 13th International Conference on Algorithmic Aspects in Information and Management

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

Steiner tree problem is a typical NP-hard problem, which has vast application background and has been an active research topic in recent years. Stochastic optimization problem is an important branch in the field of optimization. Compared with deterministic optimization problem, it is an optimization problem with random factors, and requires the use of tools such as probability and statistics, stochastic process and stochastic analysis. In this paper, we study a two-stage finite-scenario stochastic prize-collecting Steiner tree problem, where the goal is to minimize the sum of the first stage cost, the expected second stage cost and the expected penalty cost. Our main contribution is to present a primal-dual 3-approximation algorithm for this problem.

Keywords:

Mathematics Subject Classification: Primary: 90C27, 68W25.

Citation:

Full Text(HTML)

Table 1. Approximation guarantees for STP

Gilbert and Pollak [16]	$ 2 $	SIAM J. Appl. Math. 1968
Zelikovsky [30]	$ \frac{11}{6} $	Algorithmica 1993
Karpinski and Zelikovsky [24]	1.644	JOCO 1997
Prömel and Steger [25]	$ \frac{5}{3} $	J. Algorithm 2000
Robin and Zelikovsky [27]	$ 1.55 $	SIAM J. Disc. Math. 2005
Byrka et. al. [8]	$ \ln 4+\epsilon $	J. ACM 2013

| Show Table

DownLoad: CSV

Table 2. Explanation to the notations

$ p_k $	probability of scenario $ k $ being realized
$c_{e}^{k}$	purchasing cost of edge $e$ in scenario $k$
$D_k$	client (terminal vertex) set in scenario $k$
$h_k(T_k)$	penalty cost for the unserved client set $T_{k}\subseteq D_{k}\setminus r$
$(e,k)$	an edge-scenario pair ($e\in E$)
$(S,k)$	active vertex subset-scenario pair in the $k$-th scenario ($S\subset V$)
$\mathcal{E}:=\{(e,k):e\in E, k=0,1,\cdots,m\}$	edge-scenario pair set
$\mathcal{C}:=\{(S,k):S\subset V, k=0,1,\cdots,m\}$	vertex subset-scenario pair set
$\mathcal{C}_k:=\{(S,k):S\subset V\}$	the set of the vertex subset-scenario pair $(S,k)$ in scenario $k$
$\widehat{E}_{0}$	the temporarily purchased edge in the first stage
$\widehat{E}_{k}$	the temporarily purchased edge in the second stage with respect to $k$-th scenario
$\widehat{T}_{k}$	the penalty client (terminal vertex) set in the $k$-th scenario}

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Archer, M. Bateni, M. Hajiaghayi and H. Karloff, Improved approximation algorithms for prize-collecting Steiner tree and TSP, SIAM Journal on Computing, 40 (2011), 309-332. doi: 10.1137/090771429.
[2]	M. Bellare, S. Goldwass, C. Lund and A. Russell, Efficient probabilistically checkable proofs and applications to approximations, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, (1993), 294–304. doi: 10.1145/167088.167174.
[3]	P. Berman, M. Karpinski and A. Zelikovsky, 1.25-approximation algorithm for Steiner tree problem with distances 1 and 2, in Algorithms and Data Structures, (eds. F. Dehne, M. Gavrilova, J.R. Sack, C.D. Tóth), Springer Press. (2009), 86–97. doi: 10.1007/978-3-642-03367-4_8.
[4]	M. Bern and P. Plassmann, The Steiner problem with edge lengths 1 and 2, Information Processing Letters, 32 (1989), 171-176. doi: 10.1016/0020-0190(89)90039-2.
[5]	D. Bienstock, M. X. Goeman, D. Simchi-Levi and D. Williamson, A note on the prize collecting traveling salesman problem, Mathematical Programming, 59 (1993), 413-420. doi: 10.1007/BF01581256.
[6]	A. Borchers and D.-Z. Du, The $k$-Steiner ratio in graphs, SIAM Journal on Computing, 26 (1997), 857-869. doi: 10.1137/S0097539795281086.
[7]	G. Borradaile, P. Klein and C. Mathieu, An $O(n\log n)$ approximation scheme for steiner tree in planar graphs, ACM Transactions on Algorithms, 5 (2009), 1-31. doi: 10.1145/1541885.1541892.
[8]	J. Byrka, F. Grandoni, T. Rothvoß and L. Sanità, Steiner tree approximation via iterative randomized rounding, Journal of the ACM, 60 (2013), 1-33. doi: 10.1145/2432622.2432628.
[9]	M. Cheung, J. Mestre, D. B. Shmoys and J. Verschae, A primal-dual approximation algorithm for min-sum single-machine scheduling problems, SIAM Journal on Discrete Mathematics, 31 (2017), 825-838. doi: 10.1137/16M1086819.
[10]	S. Chopra and M. R. Rao, The Steiner tree problem I: Formulations, compositions and extension of facets, Mathematical Programming, 64 (1994), 209-229. doi: 10.1007/BF01582573.
[11]	S. Chopra and C.-Y. Tsai, Polyhedral approaches for the Steiner tree problem on graphs, Steiner Trees in Industry, Comb. Optim., 11, Kluwer Acad. Publ., Dordrecht, 2001,175–201. doi: 10.1007/978-1-4613-0255-1_5.
[12]	R. Cole, R. Hariharan, M. Lewenstein and E. Porat, A faster implementation of the GoemansWilliamson clustering algorithm, in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, (2001), 17–25.
[13]	D. Du, R. Lu and D. Xu, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Algorithmica, 63 (2012), 191-200. doi: 10.1007/s00453-011-9526-1.
[14]	P. Feofiloff, C. G. Fernandes, C. E. Ferreira and J. C. de. Pina, Primal-dual approximation algorithms for the prize-collecting Steiner tree problem, Information Processing Letters, 103 (2007), 195-202. doi: 10.1016/j.ipl.2007.03.012.
[15]	M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM Journal on Applied Mathematics, 32 (1977), 826-834. doi: 10.1137/0132071.
[16]	E. N. Gilbert and H. O. Pollak, Steiner minimal trees, SIAM Journal on Applied Mathematics, 16 (1968), 1-29. doi: 10.1137/0116001.
[17]	M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing, 24 (1995), 296-317. doi: 10.1137/S0097539793242618.
[18]	A. Gupta, M. Pál, R. Ravi and A. Sinha, Sampling and cost-sharing: Approximation algorithms for stochastic optimization problems, SIAM Journal on Computing, 40 (2011), 1361-1401. doi: 10.1137/080732250.
[19]	H. Heitsch and W. Römisch, Scenario reduction algorithm in stochastic programming, Computational Optimization and Applications, 24 (2003), 187-206. doi: 10.1023/A:1021805924152.
[20]	D. S. Hochbaum, Approximation algorithm for set covering and vertex cover problems, SIAM Journal on Computing, 11 (1982), 555-556. doi: 10.1137/0211045.
[21]	K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM, 48 (2001), 274-296. doi: 10.1145/375827.375845.
[22]	D. S. Johnson, M. Minkoff and S. Phillips, The prize collecting Steiner tree problem: Theory and practice, in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, (2000), 760–769.
[23]	R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum, New York, 1972, 85–103.
[24]	M. Karpinski and A. Zelikovsky, New approximation algorithms for the Steiner tree problems, Journal of Combinatorial Optimization, 1 (1997), 47-65. doi: 10.1023/A:1009758919736.
[25]	H. J. Prömel and A. Steger, A new approximation algorithm for the Steiner tree problem with performance ratio 5/3, Journal of Algorithm, 36 (2000), 89-101. doi: 10.1006/jagm.2000.1086.
[26]	R. Ravi and A. Sinha, Hedging uncertainty: Approximation algorithms for stochastic optimization problems, Mathematical Programming, 108 (2006), 97-114. doi: 10.1007/s10107-005-0673-5.
[27]	G. Robins and A. Zelikovsky, Tighter bounds for graph Steiner tree approximation, SIAM Journal on Discrete Mathematics, 19 (2005), 122-134. doi: 10.1137/S0895480101393155.
[28]	R. Schultz, L. Stougie and M. H. van der Vlerk, Two-stage stochastic integer programming: A survey, Statistica Neerlandica, 50 (1996), 404-416. doi: 10.1111/j.1467-9574.1996.tb01506.x.
[29]	D. P. Williamson, M. X. Goemans, M. Mihail and V. V. Vazirani, A primal-dual approximation algorithm for generalized steiner network problems, Combinatorica, 15 (1995), 435-454. doi: 10.1007/BF01299747.
[30]	A. Z. Zelikovsky, A faster 11/6 approximation algorithm for the Steiner problem in graphs, Information Processing Letters, 46 (1993), 79-83. doi: 10.1016/0020-0190(93)90201-J.