Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
  • 1
    Digitale Medien
    Digitale Medien
    Minimum steiner trees in normed planes (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 351-370 
    Details
    ISSN: 1432-0444
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract A minimum Steiner tree for a given setX of points is a network interconnecting the points ofX having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the “unit disk” is an arbitrary compact convex centrally symmetric domainD having nonempty interior. We show that if the boundary ofD is strictly convex and differentiable, then each edge of a full minimum Steiner tree is in one of three fixed directions. We also investigate the Steiner ratioρ(D) forD, and show that, for anyD, 0.623〈ρ(D)〈0.8686.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF02189328
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    On greedy heuristics for steiner minimum trees (1995)
    Springer
    Algorithmica 13 (1995), S. 381-386 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Steiner trees ; Greed heuristic
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We disprove a conjecture of Shor and Smith on a greedy heuristic for the Steiner minimum tree by showing that the length ratio between the Steiner minimum tree and the greedy tree constructed by their method for the same set of points can be arbitrarily close to√3/2. We also propose a new conjecture.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01293486
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    On Steiner minimal trees withL p distance (1992)
    Springer
    Algorithmica 7 (1992), S. 179-191 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Steiner trees ; Spanning trees ; Steiner ratio ; L p distance ; Bounds
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract LetL p be the plane with the distanced p (A 1 ,A 2 ) = (¦x 1 −x 2¦ p + ¦y1 −y 2¦p)/1p wherex i andy i are the cartesian coordinates of the pointA i . LetP be a finite set of points inL p . We consider Steiner minimal trees onP. It is proved that, for 1 〈p 〈 ∞, each Steiner point is of degree exactly three. Define the Steiner ratio ϱ p to be inf{L s (P)/L m (P)¦P⊂L p } whereL s (P) andL m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ϱ1 = 2/3. Chung and Graham proved ϱ2 〉 0.842. We prove in this paper that ϱ{∞} = 2/3 and √(√2/2)ϱ1ϱ2 ≤ ϱp ≤ √3/2 for anyp.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01758757
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    On better heuristics for Steiner minimum trees (1992)
    Springer
    Mathematical programming 57 (1992), S. 193-202 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Steiner trees ; approximation performance ratio
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than $${\textstyle{1 \over 2}}\sqrt 3 $$ . This solves a long-standing open problem.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581080
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 5
    Digitale Medien
    Digitale Medien
    Global convergence of Rosen's gradient projection method (1989)
    Springer
    Mathematical programming 44 (1989), S. 357-366 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Gradient projection ; algorithm ; global convergence
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract The convergence of Rosen's gradient method is a long-standing problem in nonlinear programming. Recently, progress has been made by several researchers. In this paper, we completely resolve the problem.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01587098
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 6
    Digitale Medien
    Digitale Medien
    Book Review: Discrete Analysis and operation Research (1997)
    Springer
    Journal of combinatorial optimization 1 (1997), S. 105-105 
    Details
    ISSN: 1573-2886
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1023/A:1009715104715
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 7
    Digitale Medien
    Digitale Medien
    Editorial (2000)
    Springer
    Journal of combinatorial optimization 4 (2000), S. 5-5 
    Details
    ISSN: 1573-2886
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1023/A:1009897221361
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 8
    Digitale Medien
    Digitale Medien
    Approximations for Steiner Trees with Minimum Number of Steiner Points (2000)
    Springer
    Journal of global optimization 18 (2000), S. 17-33 
    Details
    ISSN: 1573-2916
    Schlagwort(e): Steiner trees ; Approximation algorithms ; VLSI design ; WDM optical networks
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1023/A:1008384012064
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 9
    Digitale Medien
    Digitale Medien
    Book reviews (1993)
    Springer
    Journal of global optimization 3 (1993), S. 257-259 
    Details
    ISSN: 1573-2916
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01096743
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 10
    Digitale Medien
    Digitale Medien
    A continuous version of a result of Du and Hwang (1994)
    Springer
    Journal of global optimization 5 (1994), S. 127-129 
    Details
    ISSN: 1573-2916
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract In the proof of Gilbert-Pollak conjecture on the Steiner ratio, a result of Du and Hwang on a minimax problem played an important role. In this note, we prove a continuous version of this result.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01100689
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...