Combinatorial Optimization

The Steiner Ratio

Authors: Cieslik, Dietmar

Buy this book

eBook $119.00
price for USA (gross)
  • ISBN 978-1-4757-6798-8
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $159.00
price for USA
  • ISBN 978-0-7923-7015-4
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $159.00
price for USA
  • ISBN 978-1-4419-4856-4
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this book

Steiner's Problem concerns finding a shortest interconnecting network for a finite set of points in a metric space. A solution must be a tree, which is called a Steiner Minimal Tree (SMT), and may contain vertices different from the points which are to be connected. Steiner's Problem is one of the most famous combinatorial-geometrical problems, but unfortunately it is very difficult in terms of combinatorial structure as well as computational complexity. However, if only a Minimum Spanning Tree (MST) without additional vertices in the interconnecting network is sought, then it is simple to solve. So it is of interest to know what the error is if an MST is constructed instead of an SMT. The worst case for this ratio running over all finite sets is called the Steiner ratio of the space.
The book concentrates on investigating the Steiner ratio. The goal is to determine, or at least estimate, the Steiner ratio for many different metric spaces. The author shows that the description of the Steiner ratio contains many questions from geometry, optimization, and graph theory.
Audience: Researchers in network design, applied optimization, and design of algorithms.

Table of contents (12 chapters)

  • The Historical Genesis

    Cieslik, Dietmar

    Pages 1-19

  • Networks, Spaces and Algorithms

    Cieslik, Dietmar

    Pages 21-58

  • Shortest Trees in Metric Spaces — A Survey

    Cieslik, Dietmar

    Pages 59-78

  • The Steiner Ratio of Metric Spaces

    Cieslik, Dietmar

    Pages 79-98

  • The Steiner Ratio of Banach-Minkowski Spaces

    Cieslik, Dietmar

    Pages 99-130

Buy this book

eBook $119.00
price for USA (gross)
  • ISBN 978-1-4757-6798-8
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $159.00
price for USA
  • ISBN 978-0-7923-7015-4
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $159.00
price for USA
  • ISBN 978-1-4419-4856-4
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
The Steiner Ratio
Authors
Series Title
Combinatorial Optimization
Series Volume
10
Copyright
2001
Publisher
Springer US
Copyright Holder
Springer Science+Business Media Dordrecht
eBook ISBN
978-1-4757-6798-8
DOI
10.1007/978-1-4757-6798-8
Hardcover ISBN
978-0-7923-7015-4
Softcover ISBN
978-1-4419-4856-4
Series ISSN
1388-3011
Edition Number
1
Number of Pages
XII, 244
Topics