doi: 10.3934/jimo.2021116
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Received  November 2020 Revised  April 2021 Early access July 2021

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

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.

Citation: Jian Sun, Haiyun Sheng, Yuefang Sun, Donglei Du, Xiaoyan Zhang. Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2021116
References:
[1]

A. ArcherM. BateniM. 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. BienstockM. X. GoemanD. 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. BorradaileP. 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. ByrkaF. GrandoniT. 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. CheungJ. MestreD. 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. DuR. 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. FeofiloffC. G. FernandesC. 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. GuptaM. PálR. 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. SchultzL. 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. WilliamsonM. X. GoemansM. 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.

show all references

References:
[1]

A. ArcherM. BateniM. 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. BienstockM. X. GoemanD. 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. BorradaileP. 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. ByrkaF. GrandoniT. 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. CheungJ. MestreD. 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. DuR. 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. FeofiloffC. G. FernandesC. 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. GuptaM. PálR. 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. SchultzL. 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. WilliamsonM. X. GoemansM. 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.

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
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
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}
$ 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}
[1]

Feng Bao, Thomas Maier. Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems. Foundations of Data Science, 2020, 2 (1) : 1-17. doi: 10.3934/fods.2020001

[2]

Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial and Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515

[3]

Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215

[4]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks and Heterogeneous Media, 2021, 16 (1) : 1-29. doi: 10.3934/nhm.2020031

[5]

Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks and Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315

[6]

Cristian Barbarosie, Anca-Maria Toader, Sérgio Lopes. A gradient-type algorithm for constrained optimization with application to microstructure optimization. Discrete and Continuous Dynamical Systems - B, 2020, 25 (5) : 1729-1755. doi: 10.3934/dcdsb.2019249

[7]

Zhenhuan Yang, Wei Shen, Yiming Ying, Xiaoming Yuan. Stochastic AUC optimization with general loss. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4191-4212. doi: 10.3934/cpaa.2020188

[8]

Martha Garlick, James Powell, David Eyre, Thomas Robbins. Mathematically modeling PCR: An asymptotic approximation with potential for optimization. Mathematical Biosciences & Engineering, 2010, 7 (2) : 363-384. doi: 10.3934/mbe.2010.7.363

[9]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[10]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial and Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457

[11]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial and Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

[12]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142

[13]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial and Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134

[14]

Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749

[15]

Mingshang Hu. Stochastic global maximum principle for optimization with recursive utilities. Probability, Uncertainty and Quantitative Risk, 2017, 2 (0) : 1-. doi: 10.1186/s41546-017-0014-7

[16]

Alireza Goli, Hasan Khademi Zare, Reza Tavakkoli-Moghaddam, Ahmad Sadeghieh. Application of robust optimization for a product portfolio problem using an invasive weed optimization algorithm. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 187-209. doi: 10.3934/naco.2019014

[17]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial and Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[18]

Pierre Fabrie, Elodie Jaumouillé, Iraj Mortazavi, Olivier Piller. Numerical approximation of an optimization problem to reduce leakage in water distribution systems. Mathematical Control and Related Fields, 2012, 2 (2) : 101-120. doi: 10.3934/mcrf.2012.2.101

[19]

Lianshuan Shi, Enmin Feng, Huanchun Sun, Zhaosheng Feng. A two-step algorithm for layout optimization of structures with discrete variables. Journal of Industrial and Management Optimization, 2007, 3 (3) : 543-552. doi: 10.3934/jimo.2007.3.543

[20]

Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial and Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (390)
  • HTML views (373)
  • Cited by (0)

[Back to Top]