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

Steiner Trees in Industry

  • Chapter
Handbook of Combinatorial Optimization

  • 1777 Accesses

4 Conclusion

The following problems are worth studying:

  • Open problems on the Steiner ratio, such as Chung-Gilbert’s conjecture, Graham-Hwang’s conjecture, and Cielick’s conjecture, etc..

  • Find better approximation for network Steiner trees and establish an explicit lower bound for the approximation performance ratio of network Steiner trees.

  • Close the gap between the lower bound and the upper bound for the approximation performance ratio of Steiner minimum arborescence.

  • Find more efficient approximation algorithms for on-line and dynamic Steiner minimum trees and various Steiner tree packing problems.

  • Find good approximation algorithms for multi-weighted Steiner trees and multiphase Steiner trees and study close relationship between multi-weighted Steiner trees, multiphase Steiner trees, and phylogenetic trees.

  • Make clear whether there exists a polynomial-time approximation scheme for class Steiner tree in the special case with the real world background and highway interconnection problem.

  • Close the gap between the lower bound and the upper bound for the approximation performance ratio of bottleneck Steiner tree in the Euclidean plane and make clear whether there exists a polynomial-time approximation scheme for the Steiner tree with minimum number of Steiner points and bounded edge-length.

  • Implement efficient approximation algorithms to meet the requests from industries.

We believe that to attack these new and old open problems new techniques are still required and the Steiner tree is still an attractive topic for researchers in combinatorial optimization and computer science.

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 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover 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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  • E. Aharoni and R. Cohen [1998], Restricted dynamic Steiner trees for scalable multicast in datagram networks, IEEE/ACM Transactions on Networking, 6, no.3, 286–297.

    Article  Google Scholar 

  • N. Alon and Y. Azar [1993], On-line Steiner trees in the Euclidean plane, Discrete Comput. Geom. 10, no. 2, 113–121.

    MATH  MathSciNet  Google Scholar 

  • S. Arora [1996], Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of 37th FOCS, 1996, pp. 2–12.

    Google Scholar 

  • C. Beeri, R. Fagin, D. Maier, M. Yannakakis [1983], On the desirability of acyclic database schemes, J. ACM 30, 479–513.

    Article  MATH  MathSciNet  Google Scholar 

  • P. Berman and V. Ramaiyer [1994], Improved approximations for the Steiner tree problem, J. of Algorithm 17, 381–408.

    Article  MATH  MathSciNet  Google Scholar 

  • M. Bern and P. Plassmann [1989], The Steiner problem with edge lengths 1 and 2, Information Processing Letters 32, 171–176.

    Article  MATH  MathSciNet  Google Scholar 

  • R.S. Booth [1991], The Steiner ratio for five points, Discrete and Computational Geometry.

    Google Scholar 

  • A. Borchers and D.-Z. Du [1995], The k-Steiner ratio in graphs, in Proceedings of 27th STOC.

    Google Scholar 

  • A. Borchers, D.-Z. Du, B. Gao and P.-J. Wan [1998], The k-Steiner ratio in the rectilinear plane, Journal of Algorithms, 29, 1–7.

    Article  MATH  MathSciNet  Google Scholar 

  • M. Brazil, T. Cole, J.H. Rubinstein, D.A. Thomas, J.F. Weng, and N.C. Wormald [1996], Minimal Steiner trees for 2 k × 2 k square lattices. Journal of Combinatorial Theory, Series A 73, 91–110.

    Article  MATH  MathSciNet  Google Scholar 

  • P.J. Campbell [1992], Mathematics, Science and the Future, 1992 Year Book, Encyclopaedia, Britannica, Inc., London, 373–376.

    Google Scholar 

  • L.L. Cavalli-Sforza and A.W. Edwards [1967], Phylogenetic analysis: models and estimation procedures, Am. J. Human Genetics, 19, 233–257.

    Google Scholar 

  • S.-K. Chang [1972], The generation of minimal trees with a Steiner topology, J. ACM, 19, 699–711.

    Article  MATH  Google Scholar 

  • M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li [1999], Approximation algorithms for directed Steiner problems. J. Algorithms 33, no. 1, 73–91.

    Article  MATH  MathSciNet  Google Scholar 

  • D. Chen, D.-Z. Du, X. Hu, G.-H. Lin, L. Wang, and G. Xue [2000], Approximations for Steiner trees with minimum number of Steiner points, accepted by Journal of Global Optimization.

    Google Scholar 

  • F.R.K. Chung and E.N. Gilbert [1976], Steiner trees for the regular simplex, Bull. Inst. Math. Acad. Sinica, 4, 313–325.

    MATH  MathSciNet  Google Scholar 

  • F.R.K. Chung and R.L. Graham [1985], A new bound for euclidean Steiner minimum trees, Ann. N.Y. Acad. Sci., 440, 328–346.

    MATH  MathSciNet  Google Scholar 

  • F.R.K. Chung and F.K. Hwang [1978], A lower bound for the Steiner tree problem, SIAM J.Appl.Math., 34, 27–36.

    Article  MATH  MathSciNet  Google Scholar 

  • D. Cieslik [1990], The Steiner ratio of Banach-Minkowski planes, Contemporary Methods in Graph Theory (ed. R. Bodendiek), BI-Wissenschatteverlag, Mannheim, 231–248.

    Google Scholar 

  • D. Cieslik [1998], Steiner Minimal Trees, Kluwer.

    Google Scholar 

  • B.A. Cipra [1990], In math, less is more — up to a point, Science, 1081–1082.

    Google Scholar 

  • B.A. Cipra [1991], Euclidean geometry alive and well in the computer age, SIAM News, 24:1.

    Google Scholar 

  • D.-Z. Du, B. Gao, R.L. Graham, Z.-C. Liu, and P.-J. Wan [1993], Minimum Steiner trees in normed planes, Discrete and Computational Geometry, 9, 351–370.

    Article  MATH  MathSciNet  Google Scholar 

  • D.Z. Du and F.K. Hwang [1983], A new bound for the Steiner ratio, Trans. Amer. Math. Soc. 278, 137–148.

    Article  MATH  MathSciNet  Google Scholar 

  • D.Z. Du, F.K. Hwang, and E.Y. Yao [1985], The Steiner ratio conjecture is true for five points, J. Combinatorial Theory, Series A, 38, 230–240.

    Article  MATH  MathSciNet  Google Scholar 

  • D.Z. Du and F.K. Hwang [1990], The Steiner ratio conjecture of Gilbert-Pollak is true, Proceedings of National Academy of Sciences, 87, 9464–9466.

    Article  MATH  MathSciNet  Google Scholar 

  • D.-Z. Du, F.K. Hwang [1999], and G. Xue: Interconnecting highways, SIAM Discrete Mathematics 12, 252–261.

    Article  MATH  MathSciNet  Google Scholar 

  • D.-Z. Du and Z. Miller [1988], Matroids and subset interconnection design, SIAM J. Disc. Math., 1, 416–424.

    Article  MATH  MathSciNet  Google Scholar 

  • D.-Z. Du, L.-Q. Pan, and M.-T. Shing [1986], Minimum edge length guillotine rectangular partition, Report 02418-86, Math. Sci. Res. Inst., Univ. California, Berkeley, CA 1986.

    Google Scholar 

  • D.-Z. Du and P.M. Pardolas [1994], A continuous version of a result of Du and Hwang, Journal of Global Optimization, 5, 127–129.

    Article  MATH  Google Scholar 

  • D.-Z. Du and W.D. Smith [1996], Three disproofs for Gilbert-Pollak conjecture in high dimensional spaces, Journal of Combinatorial Theory, 74, 115–130.

    Article  MATH  MathSciNet  Google Scholar 

  • D.Z. Du, Y. Zhang, and Q. Feng [1991], On better heuristic for euclidean Steiner minimum trees, Proceedings 32nd FOCS, 431–439.

    Google Scholar 

  • P. Duchet [1978], Propriete de Helly et problemes de representation, in: Colloque International Paris-Orsay 260, 117–118.

    MATH  Google Scholar 

  • C. Duin [1991], T. Volgenant, The multi-weighted Steiner tree problem, Annals of Operations Research 33, 451–469.

    Article  MATH  MathSciNet  Google Scholar 

  • J. Friedel and P. Widmayer [1989], A simple proof of the Steiner ratio conjecture for five points, SIAM J. Appl. Math. 49, 960–967.

    Article  MATH  MathSciNet  Google Scholar 

  • L.R. Foulds and R.L. Graham [1982], The Steiner problem in Phylogeny is NP-complete, Advanced Applied Mathematics, 3, 43–49.

    Article  MATH  MathSciNet  Google Scholar 

  • B. Gao, D.-Z. Du, and R.L. Graham [1995], A tight lower bound for the Steiner ratio in Minkowski planes, Discrete Mathematics, 142, 49–63.

    Article  MATH  MathSciNet  Google Scholar 

  • M.R. Garey, R.L. Graham and D.S. Johnson [1977], The complexity of computing Steiner minimal trees, SIAM J. Appl. Math., 32, 835–859.

    Article  MATH  MathSciNet  Google Scholar 

  • M.R. Garey and D.S. Johnson [1997], The rectilinear Steiner tree is NP-complete, SIAM J. Appl. Math., 32, 826–834.

    Article  MathSciNet  Google Scholar 

  • E.N. Gilbert and H.O. Pollak [1968], Steiner minimal trees, SIAM J. Appl. Math., 16, 1–29.

    Article  MATH  MathSciNet  Google Scholar 

  • R.L. Graham and F.K. Hwang [1976], Remarks on Steiner minimal trees, Bull. Inst. Math. Acad. Sinica, 4, 177–182.

    MATH  MathSciNet  Google Scholar 

  • F.K. Hwang [1976], On Steiner minimal trees with rectilinear distance, SIAM J. Appl. Math., 30, 104–114.

    Article  MATH  MathSciNet  Google Scholar 

  • F.K. Hwang [1990], Flag down but sail up, Mathematical Dissemination 12:2, 5–7.

    Google Scholar 

  • F.K. Hwang, D.S. Rechards, and P. Winter [1992], Steiner tree problems North-Holland, Amsterdam.

    Google Scholar 

  • A. Iwainsky [1985], Optimal trees-a short overview on problem formulations, in A. Iwainsky (ed.) Optimization of Connections Structures in Graphs, CICIP, East Berlin, GDR, 121–133.

    Google Scholar 

  • E. Ihler, G. Reich, and P. Widmayer [1999], Class Steiner trees and VLSI-design, Discrete Applied Mathematics 90, 173–194.

    Article  MATH  MathSciNet  Google Scholar 

  • T. Jiang, E.L. Lawler, and L. Wang [1994], Aligning sequences via an evolutionary tree: complexity and approximation, Proceedings of 26th STOC.

    Google Scholar 

  • T. Jiang and L. Wang [1994], An approximation scheme for some Steiner tree problems in the plane, LNCS 834, 414–422.

    MATH  MathSciNet  Google Scholar 

  • R.M. Karp [1972], Reducibility among combinatorial problems, in R.E. Miller and J.W. Tatcher (ed.), Complexity of Computer Computation, Plenum Press, New York, 85–103.

    Google Scholar 

  • M. Karpinski and A.Z. Zelikovsky [1997], New approximation algorithms for the Steiner tree problems, Journal of Combinatorial Optimization, 1, 47–65.

    Article  MATH  MathSciNet  Google Scholar 

  • G. Kolata [1990], Solution to old puzzle: how short a shortcut? New York Times October 30.

    Google Scholar 

  • P. Korthonen [1979], An algorithm for transforming a spanning tree into a Steiner tree, Survey of Mathematical Programming (2), North-Holland, 349–357.

    Google Scholar 

  • L. Kou and K. Makki [1987], An even faster approximation algorithm for the Steiner tree problem in graph, Congressus Numerantium 59, 147–154.

    MATH  MathSciNet  Google Scholar 

  • C.-S. Li, F.F. Tong, C.J. Georgiou and M. Chen [1994], Gain equalization in metropolitan and wide area optical networks using optical amplifiers, Proc. IEEE INFOCOM’ 94, pp. 130–137, June.

    Google Scholar 

  • G.-H. Lin and G.L. Xue [1999], Steiner tree problem with minimum number of Steiner points and bounded edge-length, Information Processing Letters, 69, 53–57.

    Article  MathSciNet  Google Scholar 

  • B. Lu, J. Gu, X. Hu, and E. Shragowitz [2000], Wire segmenting for buffer insertion based on RSTP-MSP, accepted by Theoretical Computer Science.

    Google Scholar 

  • B. Lu and L. Ruan [2000], Polynomial-time approximation scheme for rectilinear Steiner arborescence problem, Journal of Combinatorial Optimization, 357–363.

    Google Scholar 

  • M.S. Manase, L.A. McGeoch, and D.D. Sleator [1988], Competitive algorithms for on-line problems, Proc. of 20th STOC, Chacago.

    Google Scholar 

  • J. S. B. Mitchell [1996], Guillotine subdivisions approximate polygonal subdivisions: A simple new method for the geometric k-MST problem, Proc. 7th ACM-SIAM Sympos. Discrete Algorithms, 402–408.

    Google Scholar 

  • J. S. B. Mitchell [1997], Guillotine subdivisions approximate polygonal subdivisions: Part III-Faster polynomial-time approximation scheme for geometric network optimization,” Proc. ninth Canadian conference on computational geometry, 229–232.

    Google Scholar 

  • J. S. B. Mitchell [1999], Guillotine subdivisions approximate polygonal subdivisions: Part II-A simple polynomial-time approximation scheme for geometric k-MST, TSP, and related problems, SIAM J. Comp. 28, 1298–1309.

    Article  MATH  Google Scholar 

  • J. S. B. Mitchell, A. Blum, P. Chalasani, and S. Vempala [1999], A constant-factor approximation for the geometric k-MST problem in the plane, SIAM J. Comp. 28, 771–781.

    Article  MATH  MathSciNet  Google Scholar 

  • I. Peterson [1990], Proven path for limiting shortest shortcut, Science News, December 22 & 29, 389.

    Google Scholar 

  • H.O. Pollak [1978], Some remarks on the Steiner problem, J. Combinatorial Theory, Ser.A, 24, 278–295.

    Article  MATH  MathSciNet  Google Scholar 

  • E. Prisner [1992], Two algorithms for the subset interconnection design, Networks 22, 385–395.

    MATH  MathSciNet  Google Scholar 

  • W.R. Pulleyblank [1995], Two Steiner tree packing problems, 27th STOC, pp.383–387.

    Google Scholar 

  • B. Ramamurthy, J. Iness and B. Mukherjee [1997], Minimizing the number of optical amplifiers needed to support a multi-wavelength optical LAN/MAN, Proc. IEEE INFOCOM’ 97, pp. 261–268, April.

    Google Scholar 

  • S.K. Rao, P. Sadayappan, F.K. Hwang, and P.W. Shor [1992], The rectilinear Steiner arborescence problem, Algorithmica 7, 277–288.

    Article  MATH  MathSciNet  Google Scholar 

  • J.H. Rubinstein and D.A. Thomas [1991], The Steiner ratio conjecture for six points, J. Combinatoria Theory, Ser.A, 58, 54–77.

    Article  MATH  MathSciNet  Google Scholar 

  • A. Sangalli [1991], Mathematicians learn how to join the dots, New Scientists April, 22.

    Google Scholar 

  • P. Schreiber [1986], On the history of the so-called Steiner weber problem, Wiss. Z. Ernst-Moritz-Arndt-Univ. Greifswald, Math.-nat.wiss. Reihe, 35, no.3.

    Google Scholar 

  • W. Shi and C. Su [2000], The rectilinear Steiner arborescence problem is NP-complete, Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA).

    Google Scholar 

  • D.D. Sleator and R.E. Tarjan [1985], Amortized efficiency of list uptate and paging rules, Commications of ACM 28, 202–208.

    Article  MathSciNet  Google Scholar 

  • J.M. Smith and J.S. Liebman [1979], Steiner trees, Steiner circuits and interference problem in building design, Engineering Optimization, 4, 15–36.

    Google Scholar 

  • J.M. Smith, D.T. Lee, and J.S. Liebman [1981], An O(N log N) heuristic for Steiner minimal tree problems in the Euclidean metric, Networks, 11, 23–39.

    MATH  MathSciNet  Google Scholar 

  • W.D. Smith [1992], How to find Steiner minimal trees in Euclidean d-space, Algorithmica, 7.

    Google Scholar 

  • W.D. Smith and P.W. Shor [1992], Steiner tree problems, Algorithmica, 7, 329–332.

    Article  MATH  MathSciNet  Google Scholar 

  • I. Stewart [1991], Trees, telephones and tiles, New Scientist 16 (1991) 26–29.

    Google Scholar 

  • R.E. Tarjan and M. Yannakakis [1984], Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput. 13, 566–579.

    Article  MATH  MathSciNet  Google Scholar 

  • Y.T. Tsai, C.Y. Tang, and Y.Y. Chen [1996], An average case analysis of a greedy algorithm for the on-line Steiner tree problem, Comput. Math. Appl. 31, no. 11, 121–131.

    Article  MATH  MathSciNet  Google Scholar 

  • P.-J. Wan, D.-Z. Du, and R.L. Graham [1997], The Steiner ratio on the dual normed plane, Discrete Mathematics 171, 261–275.

    Article  MATH  MathSciNet  Google Scholar 

  • L. Wang and D.-Z. Du [2000], Approximations for a Bottleneck Steiner Tree Problem, submitted for publication.

    Google Scholar 

  • B.M. Waxman and M. Imase [1988], Worst-case performance of Rayward-Smith’ s Steiner tree heuristic, Inform. Process. Lett. 29, 283–287.

    Article  MATH  MathSciNet  Google Scholar 

  • J. Westbrook and D.C.K. Yan [1995], The performance of greedy algorithms for the on-line Steiner tree and related problems, Math. Systems Theory 28, no. 5, 451–468.

    Article  MATH  MathSciNet  Google Scholar 

  • Y.F. Wu, P. Widmayer, and C.K. Wong [1986], A faster approximation algorithm for the Steiner problem in graphs, Acta Informatica, 23, 223–229.

    Article  MATH  MathSciNet  Google Scholar 

  • A.Z. Zelikovsky [1993], The 11/6-approximation algorithm for the Steiner problem on networks, Algorithmica 9, 463–470.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, George Washington University, DC, USA

    Xiuzhen Cheng

  2. Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, 55455

    Yingshu Li & Ding-Zhu Du

  3. Department of Computer Science and Engineering, State University of New York, Buffalo, NY, 14260

    Hung Q. Ngo

Authors
  1. Xiuzhen Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yingshu Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ding-Zhu Du
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hung Q. Ngo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of Minnesota, Minneapolis, MN

    Ding-Zhu Du

  2. University of Florida, Gainesville, FL

    Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Kluwer Academic Publishers

About this chapter

Cite this chapter

Cheng, X., Li, Y., Du, DZ., Ngo, H.Q. (2004). Steiner Trees in Industry. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/0-387-23830-1_4

Download citation

Publish with us

Policies and ethics