Advanced Search
Article Contents
Article Contents

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

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

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
  • [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.
  • 加载中



Article Metrics

HTML views(882) PDF downloads(507) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint