@prefix ns1: .
@prefix ns2: .
@prefix rdf: .
@prefix rdfs: .
@prefix xml: .
@prefix xsd: .
a ns1:Chapter ;
ns1:about ,
;
ns1:author ( ) ;
ns1:datePublished "2000" ;
ns1:datePublishedReg "2000-01-01" ;
ns1:description "Many VLSI routing applications, as well as the facility location problem involve computation of Steiner trees with non-linear cost measures. We consider two most frequent versions of this problem. In the power-p Steiner problem the cost is defined as the sum of the edge lengths where each length is raised to the power p > 1. In the bottleneck Steiner problem the objective cost is the maximum of the edge lengths. We show that the power-p Steiner problem is MAX SNP-hard and that one cannot guarantee to find a bottleneck Steiner tree within a factor less than 2, unless P = NP. We prove that in any metric space the minimum spanning tree is at most a constant times worse than the optimal power-p Steiner tree. In particular, for p = 2, we show that the minimum spanning tree is at most 23.3 times worse than the optimum and we construct an instance for which it is 17.2 times worse. We also present a better approximation algorithm for the bottleneck Steiner problem with performance guarantee log2 n, where n is the number of terminals (the minimum spanning tree can be 2 log2 n times worse than the optimum)." ;
ns1:editor ( [ a ns1:Person ;
ns1:familyName "Du" ;
ns1:givenName "Ding-Zhu" ] [ a ns1:Person ;
ns1:familyName "Smith" ;
ns1:givenName "J. M." ] [ a ns1:Person ;
ns1:familyName "Rubinstein" ;
ns1:givenName "J. H." ] ) ;
ns1:genre "chapter" ;
ns1:isAccessibleForFree false ;
ns1:isPartOf [ a ns1:Book ;
ns1:isbn "978-1-4419-4824-3",
"978-1-4757-3171-2" ;
ns1:name "Advances in Steiner Trees" ] ;
ns1:keywords "MAX SNP",
"NPs",
"SNPs",
"Steiner problem",
"Steiner tree",
"VLSI",
"algorithm",
"applications",
"approximation",
"approximation algorithm",
"best approximation algorithm",
"bottleneck Steiner tree",
"computation",
"constant time",
"cost",
"cost measures",
"edge",
"edge length",
"facility location problem",
"factors",
"frequent versions",
"instances",
"length",
"location problem",
"log2 n",
"maximum",
"measures",
"metric spaces",
"minimum spanning tree",
"number",
"number of terminals",
"objective cost",
"one",
"power",
"power P",
"problem",
"space",
"spanning tree",
"sum",
"terminals",
"time",
"trees",
"version" ;
ns1:name "On Approximation of the Power-p and Bottleneck Steiner Trees" ;
ns1:pagination "117-135" ;
ns1:productId [ a ns1:PropertyValue ;
ns1:name "doi" ;
ns1:value "10.1007/978-1-4757-3171-2_7" ],
[ a ns1:PropertyValue ;
ns1:name "dimensions_id" ;
ns1:value "pub.1035699208" ] ;
ns1:publisher [ a ns1:Organisation ;
ns1:name "Springer Nature" ] ;
ns1:sameAs ,
;
ns1:sdDatePublished "2022-10-01T06:53" ;
ns1:sdLicense "https://scigraph.springernature.com/explorer/license/" ;
ns1:sdPublisher [ a ns1:Organization ;
ns1:name "Springer Nature - SN SciGraph project" ] ;
ns1:url "https://doi.org/10.1007/978-1-4757-3171-2_7" ;
ns2:license ;
ns2:sdDataset "chapters" .
a ns1:DefinedTerm ;
ns1:inDefinedTermSet ;
ns1:name "Mathematical Sciences" .
a ns1:DefinedTerm ;
ns1:inDefinedTermSet ;
ns1:name "Applied Mathematics" .
a ns1:Person ;
ns1:affiliation ;
ns1:familyName "Zelikovsky" ;
ns1:givenName "Alexander" ;
ns1:sameAs .
a ns1:Person ;
ns1:affiliation ;
ns1:familyName "Berman" ;
ns1:givenName "Piotr" ;
ns1:sameAs .
a ns1:Organization ;
ns1:alternateName "Department of Computer Science, Georgia State University, University Plaza, 30303-3083, Atlanta, GA, USA" ;
ns1:name "Department of Computer Science, Georgia State University, University Plaza, 30303-3083, Atlanta, GA, USA" .
a ns1:Organization ;
ns1:alternateName "Department of Computer Science and Engineering, Penn State University, 16802, University Park, PA, USA" ;
ns1:name "Department of Computer Science and Engineering, Penn State University, 16802, University Park, PA, USA" .