Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Influence of Preprocessing on Steiner Tree Approximations

  • Conference paper
  • First Online:
Combinatorial Optimization and Applications

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9486))

Abstract

Given an edge-weighted graph G and a node subset R, the Steiner tree problem asks for an R-spanning tree of minimum weight. There are several strong approximation algorithms for this NP-hard problem, but research on their practicality is still in its early stages.

In this study, we investigate how the behavior of approximation algorithms changes when applying preprocessing routines first. In particular, the shrunken instances allow us to consider algorithm parameterizations that have been impractical before, shedding new light on the algorithms’ respective drawbacks and benefits.

Funded by project CH 897/1-1 of the German Research Foundation (DFG).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Article [2] is an extended version of both [1, 4], with several implementation improvements; when referring to these studies in the following, we will only cite [2].

  2. 2.

    In [5], an implementation of [3] is considered; in [2], the improved variant [9] is investigated instead, as it gives the same guarantee with a smaller runtime complexity.

  3. 3.

    This word order and abbreviation is historically common, to avoid conflicts with the established abbreviation ‘MST’ for minimum spanning tree.

  4. 4.

    Those results were obtained on different machines, with different preprocessing and memory limits. The machines are compared via the DIMACS benchmark [6]; higher is faster. We: \(\underline{375}\), 16 GB limit. PUW [17]: \(\underline{389}\), no (relevant) limit. [19]: \(\underline{307}\), no limit. All success rates are reported with respect to a 1-hour time limit.

References

  1. Beyer, S., Chimani, M.: Steiner tree 1.39-approximation in practice. In: Hliněný, P., Dvořák, Z., Jaroš, J., Kofroň, J., Kořenek, J., Matula, P., Pala, K. (eds.) MEMICS 2014. LNCS, vol. 8934, pp. 60–72. Springer, Heidelberg (2014)

    Google Scholar 

  2. Beyer, S., Chimani, M.: Strong Steiner Tree Approximations inPractice. Submitted to Journal (2014). http://arxiv.org/abs/1409.8318

  3. Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1–6:33 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  4. Chimani, M., Woste, M.: Contraction-based Steiner tree approximations in practice. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 40–49. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  5. Ciebiera, K., Godlewski, P., Sankowski, P., Wygocki, P.: Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks. arXiv abs/1410.7534 (2014). http://arxiv.org/abs/1410.7534

  6. 11th DIMACS Challenge. http://dimacs11.cs.princeton.edu. Bounds 12 September 2014

  7. Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1(3), 195–207 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fischetti, M., Leitner, M., Ljubic, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M.: Thinning out Steiner trees: a node-based model for uniform edge costs. In: 11th DIMACS Challenge (2014)

    Google Scholar 

  9. Goemans, M.X., Olver, N., Rothvoß, T., Zenklusen, R.: Matroids and integrality gaps for hypergraphic steiner tree relaxations. In: STOC 2012, pp. 1161–1176. ACM (2012)

    Google Scholar 

  10. Junger, M., Thienel, S.: The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization. Softw.: Pract. Exp. 30, 1325–1352 (2000)

    MATH  Google Scholar 

  11. Koch, T., Martin, A., Voß, S.: SteinLib: An Updated Library on Steiner Tree Problems in Graphs. ZIB-Report 00–37 (2000). http://steinlib.zib.de

  12. Kou, L.T., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta Informatica 15, 141–145 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  13. Ljubic, I., Weiskircher, R., Pferschy, U., Klau, G.W., Mutzel, P., Fischetti, M.: An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Math. Program. 105(2–3), 427–449 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  14. Mehlhorn, K.: A faster approximation algorithm for the steiner problem in graphs. Inf. Process. Lett. 27(3), 125–128 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  15. Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. In: STOC 1988, 229–234. ACM (1988)

    Google Scholar 

  16. Poggi de Aragão, M., Ribeiro, C.C., Uchoa, E., Werneck, R.F.: Hybrid local search for the steiner problem in graphs. In: MIC 2001 (2001)

    Google Scholar 

  17. Pajor, T., Uchoa, E., Werneck, R.F.: A robust and scalable algorithm for the Steiner problem in graphs. In: 11th DIMACS Challenge (2014)

    Google Scholar 

  18. Polzin, T., Vahdati Daneshmand, S.: Improved algorithms for the Steiner problem in networks. Discrete Appl. Math. 112(1–3), 263–300 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  19. Polzin, T., Vahdati Daneshmand, S.: The Steiner tree challenge: an updated study. In: 11th DIMACS Challenge (2014)

    Google Scholar 

  20. Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19(1), 122–134 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  21. Takahashi, H., Matsuyama, A.: An approximate solution for the Steiner problem in graphs. Math. Jpn. 24, 573–577 (1980)

    MathSciNet  MATH  Google Scholar 

  22. Zelikovsky, A.: An 11/6-approximation algorithm for the Steiner problem on graphs. Ann. Discrete Math. 51, 351–354 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Zelikovsky, A.: A faster approximation algorithm for the Steiner tree problem in graphs. Inf. Process. Lett. 46(2), 79–83 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  24. Zelikovsky, A.: An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9(5), 463–470 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  25. Zelikovsky, A.: Better Approximation Bounds for the Network and Euclidean Steiner Tree Problems. Technical report. CS-96-06, University of Virginia (1995)

    Google Scholar 

Download references

Acknowledgements

We thank Mihai Popa for implementations of reduction tests, and Google for funding him through the Google Summer of Code 2014 program. We also thank the authors of [8] for making their exact solver available, and Renato Werneck for detailed logs of their experiments in [17].

Author information

Authors and Affiliations

  1. Institute of Computer Science, University of Osnabrück, Osnabrück, Germany

    Stephan Beyer & Markus Chimani

Authors
  1. Stephan Beyer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Markus Chimani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stephan Beyer .

Editor information

Editors and Affiliations

  1. Dept. of Mathematics and Computer Science, Marywood University, Scranton, Pennsylvania, USA

    Zaixin Lu

  2. North Carolina Central University, Durham, North Carolina, USA

    Donghyun Kim

  3. University of Texas at Dallas, Richardson, Texas, USA

    Weili Wu

  4. Texas Southern University, Houston, Texas, USA

    Wei Li

  5. University of Texas at Dallas, Richardson, Texas, USA

    Ding-Zhu Du

Appendices

A Distribution of Solution Values

For each of the three specific instances below, we generated 2000 shufflings. The plots below show the distribution of the corresponding TM solution values.

figure a

B More Detailed Table for Influence of Preprocessing

The table below shows detailed information (number of instances, average \(\chi \) in %, and statistical data on the gaps) averaged over the instance groupings proposed in [2]. Statistical data is: the mean \(\mu \) of the gaps (averaged and how often it was better, not changed, or worse); the deviation \(\sigma \), and the skewness (how often it was negative, zero, or positive). All data is given for original and preprocessed instances; for each instance we consider 50 different random shufflings.

Group

#

avg\(\chi \)

avg \(\mu \)

# \(\mu \)

avg \(\sigma \)

# orig skew

# prep skew

orig

prep

b

n

w

orig

prep

\(<0\)

\(=0\)

\(>0\)

\(<0\)

\(=0\)

\(>0\)

EuclidSparse

15

73.68

13.06

13.73

6

1

8

15.43

17.01

0

1

14

0

2

13

EuclidComplete

14

21.11

10.84

10.84

0

14

0

13.06

13.06

0

1

13

0

1

13

RandomSparse

96

30.41

25.52

22.26

64

12

20

21.58

19.00

1

11

84

1

24

71

RandomComplete

13

9.75

31.90

25.14

7

2

4

28.53

20.86

0

2

11

0

6

7

IncidenceSparse

280

84.44

133.47

127.36

154

50

76

53.82

50.68

2

2

276

3

2

275

IncidenceComplete

73

97.84

393.61

393.61

0

73

0

88.51

88.51

0

0

73

0

0

73

ConstructedSparse

9

85.57

143.19

141.86

5

1

3

50.48

51.54

0

1

8

0

1

8

SimpleRectilinear

218

46.45

16.35

12.53

158

17

43

16.86

13.90

1

22

195

0

37

181

HardRectilinear

54

64.27

23.04

19.40

52

0

2

20.88

19.30

0

0

54

0

0

54

VLSI / Grid

206

92.36

35.49

35.76

100

12

94

27.36

27.13

1

6

199

1

5

200

WireRouting

115

98.48

0.01

0.02

28

1

86

0.44

0.51

0

5

110

0

5

110

Coverage 10

531

86.77

73.09

71.42

223

84

224

33.69

32.75

3

16

512

4

20

507

Coverage 20

130

78.27

118.35

115.13

56

34

40

40.16

38.50

1

7

122

1

8

121

Coverage 30

127

78.92

184.86

179.50

62

41

24

55.90

52.67

0

4

123

0

7

120

Coverage 40

91

71.20

25.46

21.50

73

1

17

22.79

20.82

0

0

91

0

0

91

Coverage 50

119

45.51

16.15

12.46

90

5

24

17.17

14.32

0

1

118

0

9

110

Coverage 60

41

32.33

13.61

9.44

36

1

4

15.09

10.88

1

2

38

0

12

29

Coverage 70

18

14.77

8.01

3.60

12

4

2

9.62

6.04

0

8

10

0

8

10

Coverage 80

11

9.06

4.89

3.09

5

6

0

6.56

4.56

0

6

5

0

6

5

Coverage 90

14

5.87

3.47

1.95

11

2

1

7.32

5.02

0

2

12

0

4

10

Coverage 100

11

0.75

1.11

0.22

6

5

0

3.31

0.89

0

5

6

0

9

2

All

1093

73.15

75.69

72.86

574

183

336

32.32

30.53

5

51

1037

5

83

1005

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Beyer, S., Chimani, M. (2015). The Influence of Preprocessing on Steiner Tree Approximations. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, DZ. (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science(), vol 9486. Springer, Cham. https://doi.org/10.1007/978-3-319-26626-8_44

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-26626-8_44

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-26625-1

  • Online ISBN: 978-3-319-26626-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation