Approaching the 5/4-approximation for rectilinear Steiner trees

Piotr Berman; Ulrich Fößmeier; Marek Karpinski; Michael Kaufmann; Alexander Zelikovsky

doi:10.1007/bfb0049397

Approaching the 5/4-approximation for rectilinear Steiner trees

Piotr Berman, Ulrich Fößmeier, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

The rectilinear Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in the plane with rectilinear distance. We show that the performance ratios of Zelikovsky’s[17] heuristic is between 1.3 and 1.3125 (before it was only bounded from above by 1.375), while the performance ratio of the heuristic of Berman and Ramaiyer[l] is at most 1.271 (while the previous bound was 1.347). Moreover, we provide (formula Presented)-time algorithms that satisfy these performance ratios.

Original language	English (US)
Title of host publication	Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings
Editors	Jan van Leeuwen
Publisher	Springer Verlag
Pages	60-71
Number of pages	12
ISBN (Print)	9783540584346
DOIs	https://doi.org/10.1007/bfb0049397
State	Published - 1994
Event	2nd Annual European Symposium on Algorithms, ESA 1994 - Utrecht, Netherlands Duration: Sep 26 1994 → Sep 28 1994

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	855 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	2nd Annual European Symposium on Algorithms, ESA 1994
Country/Territory	Netherlands
City	Utrecht
Period	9/26/94 → 9/28/94

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0049397

Cite this

Berman, P., Fößmeier, U., Karpinski, M., Kaufmann, M., & Zelikovsky, A. (1994). Approaching the 5/4-approximation for rectilinear Steiner trees. In J. van Leeuwen (Ed.), Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings (pp. 60-71). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 855 LNCS). Springer Verlag. https://doi.org/10.1007/bfb0049397

Berman, Piotr ; Fößmeier, Ulrich ; Karpinski, Marek et al. / Approaching the 5/4-approximation for rectilinear Steiner trees. Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings. editor / Jan van Leeuwen. Springer Verlag, 1994. pp. 60-71 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{38af22c15fc5401b9677d608a2c685a6,

title = "Approaching the 5/4-approximation for rectilinear Steiner trees",

abstract = "The rectilinear Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in the plane with rectilinear distance. We show that the performance ratios of Zelikovsky{\textquoteright}s[17] heuristic is between 1.3 and 1.3125 (before it was only bounded from above by 1.375), while the performance ratio of the heuristic of Berman and Ramaiyer[l] is at most 1.271 (while the previous bound was 1.347). Moreover, we provide (formula Presented)-time algorithms that satisfy these performance ratios.",

author = "Piotr Berman and Ulrich F{\"o}{\ss}meier and Marek Karpinski and Michael Kaufmann and Alexander Zelikovsky",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1994.; 2nd Annual European Symposium on Algorithms, ESA 1994 ; Conference date: 26-09-1994 Through 28-09-1994",

year = "1994",

doi = "10.1007/bfb0049397",

language = "English (US)",

isbn = "9783540584346",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "60--71",

editor = "{van Leeuwen}, Jan",

booktitle = "Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings",

address = "Germany",

}

Berman, P, Fößmeier, U, Karpinski, M, Kaufmann, M & Zelikovsky, A 1994, Approaching the 5/4-approximation for rectilinear Steiner trees. in J van Leeuwen (ed.), Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 855 LNCS, Springer Verlag, pp. 60-71, 2nd Annual European Symposium on Algorithms, ESA 1994, Utrecht, Netherlands, 9/26/94. https://doi.org/10.1007/bfb0049397

Approaching the 5/4-approximation for rectilinear Steiner trees. / Berman, Piotr; Fößmeier, Ulrich; Karpinski, Marek et al.
Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings. ed. / Jan van Leeuwen. Springer Verlag, 1994. p. 60-71 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 855 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approaching the 5/4-approximation for rectilinear Steiner trees

AU - Berman, Piotr

AU - Fößmeier, Ulrich

AU - Karpinski, Marek

AU - Kaufmann, Michael

AU - Zelikovsky, Alexander

PY - 1994

Y1 - 1994

N2 - The rectilinear Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in the plane with rectilinear distance. We show that the performance ratios of Zelikovsky’s[17] heuristic is between 1.3 and 1.3125 (before it was only bounded from above by 1.375), while the performance ratio of the heuristic of Berman and Ramaiyer[l] is at most 1.271 (while the previous bound was 1.347). Moreover, we provide (formula Presented)-time algorithms that satisfy these performance ratios.

AB - The rectilinear Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in the plane with rectilinear distance. We show that the performance ratios of Zelikovsky’s[17] heuristic is between 1.3 and 1.3125 (before it was only bounded from above by 1.375), while the performance ratio of the heuristic of Berman and Ramaiyer[l] is at most 1.271 (while the previous bound was 1.347). Moreover, we provide (formula Presented)-time algorithms that satisfy these performance ratios.

UR - http://www.scopus.com/inward/record.url?scp=21844493616&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21844493616&partnerID=8YFLogxK

U2 - 10.1007/bfb0049397

DO - 10.1007/bfb0049397

M3 - Conference contribution

AN - SCOPUS:21844493616

SN - 9783540584346

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 60

EP - 71

BT - Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings

A2 - van Leeuwen, Jan

PB - Springer Verlag

T2 - 2nd Annual European Symposium on Algorithms, ESA 1994

Y2 - 26 September 1994 through 28 September 1994

ER -

Berman P, Fößmeier U, Karpinski M, Kaufmann M, Zelikovsky A. Approaching the 5/4-approximation for rectilinear Steiner trees. In van Leeuwen J, editor, Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings. Springer Verlag. 1994. p. 60-71. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0049397

Approaching the 5/4-approximation for rectilinear Steiner trees

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this