Bibliography

1

A. Aazami, J. Cheriyan, and K. Jampani.
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs.
In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 5687 of LNCS, pages 1-14. 2009.

2

A.K. Abu-Affash, P Carmi, and M.J. Katz.
Bottleneck Steiner Tree with Bounded Number of Steiner Vertices.
In CCCG, pages 39-42, 2011.

3

A. Agrawal, P. Klein, and R. Ravi.
When trees collide: An approximation algorithm for the generalized Steiner problem on networks.
In Proceedings of the twenty-third Annual ACM Symposium on Theory of Computing, pages 134-144. ACM, 1991.

4

N. Alon, B. Chor, F. Pardi, and A. Rapoport.
Approximate Maximum Parsimony and Ancestral Maximum Likelihood.
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 7:183-187, 2010.

5

E. Althaus, G. Calinescu, I. Mandoiu, S. K. Prasad, N. Tchervenski, and A. Zelikovsky.
Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks.
Wireless Networks, 12(3):287-299, 2006.

6

A. Archer, M.H. Bateni, M.T. Hajiaghayi, and H. Karloff.
Improved approximation algorithms for prize-collecting Steiner tree and TSP.
SIAM Journal on Computing, 40(2):309-332, 2011.

7

S. Arora.
Polynomial Time Approximation Schemes for Euclidean TSP and other Geometric Problems.
Journal of the ACM, 45(5):753-782, 1998.

8

S.W. Bae, C. Lee, and S. Choi.
On exact solutions to the Euclidean bottleneck Steiner tree problem.
Information Processing Letters, 110(16):672-678, 2010.

9

M. H. Bateni, M. T. Hajiaghayi, and D. Marx.
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth.
CoRR, abs/0911.5143, also appeared in Journal of the ACM, 58(5), 2011.

10

P. Berman, A. Bhattacharyya, K. Makarychev, S. Raskhodnikova, and G. Yaroslavtsev.
Approximation Algorithms for Spanner Problems and Directed Steiner Forest.
Information and Computation, 222:93 - 107, 2013.

11

P. Berman, M. Karpinski, and A. Zelikovsky.
1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2.
Proc. of the 11th Workshop on Algorithms and Data Structures. LNCS 5664, pages 86-97, 2009.

12

P. Berman, M.Karpinski, and A. Zelikovsky.
A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two.
CoRR, abs/0812.2137, 2008. Also appeared in Proc. of the 21st International Symposium on Algorithms and Computation, 6506:15-24, 2010.

13

M. Bern and P. Plassmann.
The Steiner problem with edge lengths 1 and 2.
Information Processing Letters, 32(4):171-176, 1989.

14

Ahmad Biniaz, Anil Maheshwari, and Michiel Smid.
An optimal algorithm for the Euclidean bottleneck full Steiner tree problem.
Computational Geometry: Theory and Applications, 47(3):377-380, 2014.

15

Ahmad Biniaz, Anil Maheshwari, and Michiel Smid.
Approximating Full Steiner Tree in a Unit Disk Graph.
In Proceedings of the 26th Canadian Conference in Computational Geometry (CCCG 2014), pages 113-117, 2014.

16

Ahmad Biniaz, Anil Maheshwari, and Michiel Smid.
On the Hardness of Full Steiner Tree Problems.
Technical report, Carleton University, 2014.

17

K.D. Boese and A.B. Kahng.
Zero-skew clock routing trees with minimum wirelength.
In ASIC Conference and Exhibit, 1992., Proceedings of Fifth Annual IEEE International, pages 17-21. IEEE, 1992.

18

I. Bomze, M. Chimani, M. Junger, I. Ljubi, P. Mutzel, and B. Zey.
Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut.
Algorithms and Computation, pages 427-439, 2010.

19

B. Borradaile, N. Klein, and C. Mathieu.
An (n log n ) approximation scheme for Steiner tree in planar graphs.
ACM Transactions on Algorithms, 5(3), 2009.

20

G. Borradaile, P. N. Klein, and C. Mathieu.
A Polynomial-time Approximation Scheme for Euclidean Steiner Forest.
CoRR, abs/1302.7270, 2013.

21

J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità.
An improved LP-based Approximation for Steiner Tree.
In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 583-592, 2010.

22

M. agalj, J.P. Hubaux, and C.C. Enz.
Energy-efficient broadcasting in all-wireless networks.
Wireless Networks, 11(1):177-188, 2005.

23

G. Calinescu.
Approximate Min-Power Strong Connectivity.
SIAM Journal on Discrete Mathematics, 27(3):1527-1543, 2013.

24

G. Calinescu and A. Zelikovsky.
The polymatroid steiner problems.
Journal of Combinatorial Optimization, 9(3):281-294, 2005.

25

J. Cardinal, M. Karpinski, R. Schmied, and C. Viehmann.
Approximating subdense instances of covering problems.
In Proceedings of the 6th Latin-American Algorithms, Graphs and Optimization Symposium, pages 59-65, 2011.

26

T.H. Chao, J.M. Ho, and Y.C. Hsu.
Zero skew clock net routing.
In Proceedings of the 29th ACM/IEEE Design Automation Conference, pages 518-523. IEEE Computer Society Press, 1992.

27

M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li.
Approximation algorithms for directed Steiner problems.
In Proceedings of the ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 192-200. Society for Industrial and Applied Mathematics, 1998.

28

M. Charikar, J. Kleinberg, R. Kumar, S. Rajagopalan, A. Sahai, and A. Tomkins.
Minimizing wirelength in zero and bounded skew clock trees.
In Proceedings of the tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 177-184. Society for Industrial and Applied Mathematics, 1999.

29

C. Chekuri, A. Ene, and N. Korula.
Prize-Collecting Steiner Tree and Forest in Planar Graphs.
CoRR, abs/1006.4357, 2010.

30

C. Chekuri, A. Ene, and A. Vakilian.
Node-Weighted Network Design in Planar and Minor-closed Families of Graphs.
In Proc. 39th International Colloquium Conference on Automata, Languages, and Programming, pages 206-217, 2012.

31

C. Chekuri, A. Ene, and A. Vakilian.
Prize-collecting Survivable Network Design in Node-weighted Graphs.
In Proc. 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 98-109, 2012.

32

C. Chekuri, G. Even, and G. Kortsarz.
A combinatorial approximation algorithm for the group Steiner problem.
Discrete Applied Mathematics, 154(1):15-34, 2006.

33

Y. Chen.
An Improved Approximation Algorithm for the Terminal Steiner Tree Problem.
In Computational Science and Its Applications - ICCSA 2011, volume 6784 of LNCS, pages 141-151. 2011.

34

J. Cheriyan and M.R. Salavatipour.
Hardness and approximation results for packing Steiner trees.
Algorithmica, 45(1):21-43, 2006.

35

R.H. Chitnis, H. Esfandiari, M.T. Hajiaghayi, R. Khandekar, G. Kortsarz, and S. Seddighin.
A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands.
In Proc. International Symposium on Parameterized and Exact Computation, pages 159-171, 2014.

36

M. Chlebik and J. Chlebikova.
The Steiner tree problem on graphs: Inapproximability results.
Theoretical Computer Science, 406(3):207-214, 2008.

37

A.E.F. Clementi, P. Penna, and R. Silvestri.
On the power assignment problem in radio networks.
Electronic Colloquium on Computational Complexity (ECCC), 7(54), 2000.

38

N. Cohen and Z. Nutov.
A (1+ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius.
Theoretical Computer Science, 489–490:67 - 74, 2013.

39

A.M. Costa, J.F. Cordeau, and G. Laporte.
Steiner tree problems with profits.
Information Systems and Operational Research, 44(2):99-116, 2006.

40

E. Demaine, M.T. Hajiaghayi, and P. Klein.
Node-weighted steiner tree and group steiner tree in planar graphs.
Automata, Languages and Programming, pages 328-340, 2009.

41

D. Du and X. Hu.
Steiner Tree Problems in Computer Communication Networks.
World Scientific Publishing, 2008.

42

C.W. Duin and A. Volgenant.
The partial sum criterion for Steiner trees in graphs and shortest paths.
European Journal of Operations Research, 97:172-182, 1997.

43

M. Edahiro.
Minimum skew and minimum path length routing in VLSI layout design.
NEC research & development, 32(4):569-575, 1991.

44

Ö. Egecioglu, T.F. Gonzalez, and T.L.F. Gonzalez.
Minimum-energy broadcast in simple graphs with limited node power.
In in Proc. IASTED Int. Conf. on Parallel and Distributed Computing and Systems, pages 334-338. Citeseer, 2001.

45

A. Ene and A. Vakilian.
Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements.
In Proc. 46th ACM Symposium on Theory of Computing, pages 754-763, 2014.

46

R.E. Erickson, C.L. Monma, and A.F. Veinott Jr.
Send-and-split method for minimum-concave-cost network flows.
Math. Oper. Res., 12 (4):634-664, 1987.

47

M. Feldman, G. Kortsarz, and Z. Nutov.
Improved approximating algorithms for directed steiner forest.
In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 922-931. Society for Industrial and Applied Mathematics, 2009.

48

D. Fernández-Baca and J. Lagergren.
On the approximability of the Steiner tree problem in phylogeny.
Algorithms and Computation, pages 65-74, 1996.

49

L. Fleischer, J. Konemann, S. Leonardi, and G. Schafer.
Simple cost sharing schemes for multicommodity rent-or-buy and stochastic steiner tree.
In Proceedings of the thirty-eighth Annual ACM Symposium on Theory of Computing, pages 663-670. ACM, 2006.

50

G. Frederickson and J. Jaja.
On the Relationship between the Biconnectivity Augmentation and Travelling Salesman Problems.
Theoretical Computer Science, 19:189 - 201, 1982.

51

T. Fukunaga.
Spider covers for prize-collecting network activation problem.
To appear in Proc. ACM-SIAM Symposium on Discrete Algorithms, 2015.

52

M.R. Garey and D.S. Johnson.
Computers and Intractability: A Guide to the Theory of NP-completeness.
WH Freeman & Co. New York, NY, USA, 1979.

53

N. Garg, G. Konjevod, and R. Ravi.
A polylogarithmic approximation algorithm for the group Steiner tree problem.
In Proceedings of the ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 253-259. Society for Industrial and Applied Mathematics, 1998.

54

S. Guha and S. Khuller.
Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets.
Information and Computation, 150(1):57-74, 1999.

55

A. Gupta and A. Kumar.
A constant-factor approximation for stochastic Steiner forest.
In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC '09, pages 659-668, New York, NY, USA, 2009. ACM.

56

A. Gupta, M. Pál, R. Ravi, and A. Sinha.
Boosted Sampling: Approximation Algorithms for Stochastic Optimization.
In Proc. of the thirty-sixth Annual ACM Symposium on Theory of Computing, pages 417-426, 2004.

57

M.T. Hajiaghayi and Kamal Jain.
The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema.
In Proceedings of the seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pages 631-640, 2006.

58

M.T. Hajiaghayi, G. Kortsarz, and M. Salavatipour.
Approximating Buy-at-Bulk and Shallow-light k-Steiner trees.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 152-163, 2006.

59

M.T. Hajiaghayi, V. Liaghat, and D. Panigrahi.
Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems.
In Proc. 41th International Colloquium Conference on Automata, Languages, and Programming, pages 576-587, 2014.

60

E. Halperin, G. Kortsarz, R. Krauthgamer, A. Srinivasan, and N. Wang.
Integrality ratio for group Steiner trees and directed Steiner trees.
In Proceedings of the fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 275-284. Society for Industrial and Applied Mathematics, 2003.

61

E. Halperin and R. Krauthgamer.
Polylogarithmic inapproximability.
In Proceedings of the thirty-fifth Annual ACM Symposium on Theory of Computing, pages 585-594. ACM, 2003.

62

F. Hargesheimer.
A Note on the Prize Collecting Bottleneck TSP and Related Problems.
CS Report 85336, University of Bonn, 2013.

63

F. Hargesheimer.
Prize Collecting Bottleneck Steiner Problems: A Combinatorial Approach.
CS Report 85345, University of Bonn, 2013.

64

M. Hauptmann.
On the Approximability of Dense Steiner Problems.
Journal of Discrete Algorithms, 21:41-51, 2013.

65

M. Hauptmann and M Lamp.
Approximability of Selected Phylogenetic Tree Problems.
CS Report 85299, University of Bonn, 2008. Also submitted to the Journal of Discrete Algorithms.

66

S. Held and N. Kaemmerling.
Two-Level Rectilinear Steiner Trees.
CoRR, abs/1501.00933v1, 2015.

67

D. Hoshika and E. Miyano.
Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes.
In Algorithmic Aspects in Information and Management, volume 8546 of LNCS, pages 100-111. 2014.

68

S. Hougardy, J. Silvanus, and J. Vygen.
Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm.
CoRR, abs/1406.0492v2, 2014.

69

S. Hsieh, H. Gao, and S. Yang.
On the Internal Steiner Tree Problem.
In Theory and Applications of Models of Computation, volume 4484 of LNCS, pages 274-283. Springer-Verlag Berlin Heidelberg, 2007.

70

C. Huang, C. Lee, H. Gao, and S. Hsieh.
The internal Steiner tree problem: Hardness and approximations.
Journal of Complexity, 29:27-43, 2013.

71

D.S. Johnson, M. Minkoff, and S. Phillips.
The prize collecting steiner tree problem: theory and practice.
In Proceedings of the eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 760-769. Society for Industrial and Applied Mathematics, 2000.

72

M. Karpinski, I. Mandoiu, A. Olshevsky, and A. Zelikovsky.
Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem.
Proc. of the 8th Workshop on Algorithms and Data Structures. LNCS 2748, pages 401-411, 2003.

73

M. Karpinski and A. Zelikovsky.
New Approximation Algorithms for the Steiner Tree Problems.
Journal of Combinatorial Optimization, 1(1):47-65, 1997.

74

M. Karpinski and A. Zelikovsky.
Approximating dense cases of covering problems.
In Network Design: Connectivity and Facilities Location (Princeton, NJ, 1997), volume 40 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 169-178. 1998.

75

S. Khuller and A. Zhu.
The general Steiner tree-star problem.
Information Processing Letters, 84(4):215-220, 2002.

76

P.N. Klein and R. Ravi.
A Nearly Best-possible Approximation Algorithm for Node-Weighted Steiner Trees.
J. Algorithms, 19(1):104-115, 1995.

77

J. Koenemann, S. Sadeghian, and L. Sanita.
An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree.
In Proc. 54th Annual IEEE Symposium on Foundations of Computer Science, 2013.

78

G. Kortsarz and D. Peleg.
Approximation algorithms for minimum-time broadcast.
SIAM Journal on Discrete Mathematics, 8(3):401-427, 1995.

79

G. Kortsarz and D. Peleg.
Approximating the weight of shallow Steiner trees.
Discrete Applied Mathematics, 93(2-3):265-285, 1999.

80

Y. Lando and Z. Nutov.
Inapproximability of survivable networks.
Theoretical Computer Science, 410(21-23):2122-2125, 2009.

81

L.C. Lau.
Packing Steiner Forests.
Integer Programming and Combinatorial Optimization, pages 362-376, 2005.

82

L.C. Lau and H. Zhou.
A Unified Algorithm for Degree Bounded Survivable Network Design.
Integer Programming and Combinatorial Optimization, pages 369-380, 2014.

83

A. Levin.
A Better Approximation Algorithm for the Budget Prize Collecting Tree Problem.
Operations Research Letters, 32(4):316 - 319, 2004.

84

X. Li, X.H. Xu, F. Zou, H. Du, P. Wan, Y. Wang, and W. Wu.
A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs.
Combinatorial Optimization and Applications, pages 36-48, 2009.

85

Z.M. Li, D.M. Zhu, and S.H. Ma.
Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane.
Journal of Computer Science and Technology, 19(6):791-794, 2004.

86

W. Liang.
Constructing minimum-energy broadcast trees in wireless ad hoc networks.
In Proceedings of the 3rd ACM International Symposium on Mobile ad hoc Networking & Computing, pages 112-122, 2002.

87

C. Lung Lu, C. Yi Tang, and R. Chia-Tung Lee.
The Full Steiner Tree Problem.
Theoretical Computer Science, 306:55-67, 2003.

88

M.V. Marathe, R. Ravi, R. Sundaram, SS Ravi, D.J. Rosenkrantz, and H.B. Hunt III.
Bicriteria network design problems.
Arxiv preprint cs/9809103, 1998.

89

P. Mirchandani.
The multi-tier tree problem.
INFORMS Journal on Computing, 8(3):202-218, 1996.

90

A. Moss and Y. Rabani.
Approximation algorithms for constrained node weighted steiner tree problems.
SIAM J. Comput., 2(37):460-481, 2007.

91

J. Naor, D. Panigrahi, and M. Singh.
Online Node-weighted Steiner Tree and Related Problems.
In Proc. 52th Annual IEEE Symposium on Foundations of Computer Science, pages 210-219, 2011.

92

Z. Nutov.
Approximating Steiner Network Activation Problems.
In Proc. 10th Latin American Symposium on Theoretical Informatics, pages 594-605, 2012.

93

D. Panigrahi.
Survivable Network Design Problems in Wireless Networks.
In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1014-1027, 2011.

94

I. Papadimitriou and L. Georgiadis.
Minimum-energy broadcasting in multi-hop wireless networks using a single broadcast tree.
Mobile Networks and Applications, 11(3):361-375, 2006.

95

H. J. Prömel and A. Steger.
A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3.
J. Algorithms, 36(1):89-101, 2000.

96

R. Ravi.
Rapid rumor ramification: Approximating the minimum broadcast time.
Proc. of the 35th Annual Symposium on Foundations of Computer Science, pages 202-213, 1994.

97

G. Robins and A. Zelikovsky.
Improved Steiner Tree Approximation in Graphs.
In Proceedings of the eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770-779. Society for Industrial and Applied Mathematics, 2000.

98

G. Robins and A. Zelikovsky.
Tighter Bounds for Graph Steiner Tree Approximation.
SIAM J. Discrete Math., 1(19):122-134, 2006.

99

M. Sarrafzadeh and C.K. Wong.
Bottleneck Steiner trees in the plane.
IEEE Transactions on Computers, 41(3):370-374, 1992.

100

Y. Sharma, C. Swamy, and D.P. Williamson.
Approximation algorithms for prize collecting forest problems with submodular penalty functions.
In Proceedings of the eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1275-1284, 2007.

101

C. Swamy and D.B. Shmoys.
Approximation algorithms for 2-stage stochastic optimization problems.
ACM SIGACT News, 37(1):33-46, 2006.

102

L. Trevisan.
When Hamming meets Euclid: The Approximability of Geometric TSP and MST.
SIAM J. on Computing, 2(30):475-485, 2001.

103

L. Wang and D.Z. Du.
Approximations for a bottleneck Steiner tree problem.
Algorithmica, 32(4):554-561, 2002.

104

L. Wang, T. Jiang, and E.L. Lawler.
Approximation algorithms for tree alignment with a given phylogeny.
Algorithmica, 16(3):302-315, 1996.

105

L. Wang and Z. Li.
An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane.
Information Processing Letters, 81(3):151-156, 2002.

106

D. Watel, M. A. Weisser, C. Bentz, and D. Barth.
Steiner Problems with Limited Number of Branching Nodes.
In Structural Information and Communication Complexity, volume 8179 of LNCS, pages 310-321. 2013.

107

B. Wu.
A simple approximation algorithm for the internal Steiner minimum tree.
Computing Research Repository (CoRR), arXiv:1307.3822, 2013.

108

A. Zelikovsky.
An 11/6-Approximation Algorithm for the Network Steiner Problem.
Algorithmica, 9(5):463-470, 1993.

109

A. Zelikovsky.
A series of approximation algorithms for the acyclic directed Steiner tree problem.
Algorithmica, 18(1):99-110, 1997.

110

A. Zelikovsky and I.I. Mndoiu.
Practical approximation algorithms for zero-and bounded-skew trees.
In Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 407-416. Society for Industrial and Applied Mathematics, 2001.

111

P. Zhang.
An approximation algorithm to the k-Steiner forest problem.
Theory and Applications of Models of Computation, pages 728-737, 2007.

  
$\Box$