On Approximation of the Power-p and Bottleneck Steiner Trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

Piotr Berman , Alexander Zelikovsky

ABSTRACT

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). More... »

PAGES

117-135

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4757-3171-2_7

DOI

http://dx.doi.org/10.1007/978-1-4757-3171-2_7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1035699208


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Penn State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Penn State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Georgia State University, University Plaza, 30303-3083, Atlanta, GA, USA", 
          "id": "http://www.grid.ac/institutes/grid.256304.6", 
          "name": [
            "Department of Computer Science, Georgia State University, University Plaza, 30303-3083, Atlanta, GA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zelikovsky", 
        "givenName": "Alexander", 
        "id": "sg:person.01121041073.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "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).", 
    "editor": [
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Smith", 
        "givenName": "J. M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Rubinstein", 
        "givenName": "J. H.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-1-4757-3171-2_7", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-1-4419-4824-3", 
        "978-1-4757-3171-2"
      ], 
      "name": "Advances in Steiner Trees", 
      "type": "Book"
    }, 
    "keywords": [
      "power P", 
      "objective cost", 
      "edge length", 
      "VLSI", 
      "cost", 
      "bottleneck Steiner tree", 
      "location problem", 
      "facility location problem", 
      "problem", 
      "power", 
      "applications", 
      "time", 
      "length", 
      "edge", 
      "frequent versions", 
      "computation", 
      "algorithm", 
      "maximum", 
      "approximation", 
      "constant time", 
      "terminals", 
      "Steiner problem", 
      "one", 
      "Steiner tree", 
      "number of terminals", 
      "cost measures", 
      "NPs", 
      "space", 
      "minimum spanning tree", 
      "number", 
      "sum", 
      "spanning tree", 
      "version", 
      "factors", 
      "instances", 
      "trees", 
      "log2 n", 
      "approximation algorithm", 
      "measures", 
      "metric spaces", 
      "best approximation algorithm", 
      "MAX SNP", 
      "SNPs"
    ], 
    "name": "On Approximation of the Power-p and Bottleneck Steiner Trees", 
    "pagination": "117-135", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035699208"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-1-4757-3171-2_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-1-4757-3171-2_7", 
      "https://app.dimensions.ai/details/publication/pub.1035699208"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:22", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_467.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-1-4757-3171-2_7"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-1-4757-3171-2_7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-1-4757-3171-2_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4757-3171-2_7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4757-3171-2_7'


 

This table displays all metadata directly associated to this object as RDF triples.

122 TRIPLES      22 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-1-4757-3171-2_7 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N3b8b9443f21d40f586fb523cb87755a9
4 schema:datePublished 2000
5 schema:datePublishedReg 2000-01-01
6 schema: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).
7 schema:editor N26dfe8bad82a4fbaac16e4eb18edcea0
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Ne131f6570b914e399d513133f4ae9c86
11 schema:keywords MAX SNP
12 NPs
13 SNPs
14 Steiner problem
15 Steiner tree
16 VLSI
17 algorithm
18 applications
19 approximation
20 approximation algorithm
21 best approximation algorithm
22 bottleneck Steiner tree
23 computation
24 constant time
25 cost
26 cost measures
27 edge
28 edge length
29 facility location problem
30 factors
31 frequent versions
32 instances
33 length
34 location problem
35 log2 n
36 maximum
37 measures
38 metric spaces
39 minimum spanning tree
40 number
41 number of terminals
42 objective cost
43 one
44 power
45 power P
46 problem
47 space
48 spanning tree
49 sum
50 terminals
51 time
52 trees
53 version
54 schema:name On Approximation of the Power-p and Bottleneck Steiner Trees
55 schema:pagination 117-135
56 schema:productId N18d24f20f7e241859061387438ddc725
57 Nfb8d69e55bee4689b871ad6903da082a
58 schema:publisher N194e49dc39c4401791b88964af6583b0
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035699208
60 https://doi.org/10.1007/978-1-4757-3171-2_7
61 schema:sdDatePublished 2022-08-04T17:22
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N57327a3df79241979c85498798f6ec5c
64 schema:url https://doi.org/10.1007/978-1-4757-3171-2_7
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N18d24f20f7e241859061387438ddc725 schema:name doi
69 schema:value 10.1007/978-1-4757-3171-2_7
70 rdf:type schema:PropertyValue
71 N194e49dc39c4401791b88964af6583b0 schema:name Springer Nature
72 rdf:type schema:Organisation
73 N22ccbab7d33c47a1bdbd855129c7694f schema:familyName Smith
74 schema:givenName J. M.
75 rdf:type schema:Person
76 N25e9d82bc98b43e08986bc12bdbe8f56 rdf:first N22ccbab7d33c47a1bdbd855129c7694f
77 rdf:rest N49e344bd9e6a45c985525fb479b3efc5
78 N26dfe8bad82a4fbaac16e4eb18edcea0 rdf:first N69ea29ccc71d4190bec754d38e8c69d1
79 rdf:rest N25e9d82bc98b43e08986bc12bdbe8f56
80 N3b8b9443f21d40f586fb523cb87755a9 rdf:first sg:person.01274506210.27
81 rdf:rest N431591dbf93144da9a0a808b8e88a212
82 N431591dbf93144da9a0a808b8e88a212 rdf:first sg:person.01121041073.51
83 rdf:rest rdf:nil
84 N49e344bd9e6a45c985525fb479b3efc5 rdf:first N8d24c7e2b94a4a9cbd1b70b54ac2ae4e
85 rdf:rest rdf:nil
86 N57327a3df79241979c85498798f6ec5c schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N69ea29ccc71d4190bec754d38e8c69d1 schema:familyName Du
89 schema:givenName Ding-Zhu
90 rdf:type schema:Person
91 N8d24c7e2b94a4a9cbd1b70b54ac2ae4e schema:familyName Rubinstein
92 schema:givenName J. H.
93 rdf:type schema:Person
94 Ne131f6570b914e399d513133f4ae9c86 schema:isbn 978-1-4419-4824-3
95 978-1-4757-3171-2
96 schema:name Advances in Steiner Trees
97 rdf:type schema:Book
98 Nfb8d69e55bee4689b871ad6903da082a schema:name dimensions_id
99 schema:value pub.1035699208
100 rdf:type schema:PropertyValue
101 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
102 schema:name Mathematical Sciences
103 rdf:type schema:DefinedTerm
104 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
105 schema:name Applied Mathematics
106 rdf:type schema:DefinedTerm
107 sg:person.01121041073.51 schema:affiliation grid-institutes:grid.256304.6
108 schema:familyName Zelikovsky
109 schema:givenName Alexander
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51
111 rdf:type schema:Person
112 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
113 schema:familyName Berman
114 schema:givenName Piotr
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
116 rdf:type schema:Person
117 grid-institutes:grid.256304.6 schema:alternateName Department of Computer Science, Georgia State University, University Plaza, 30303-3083, Atlanta, GA, USA
118 schema:name Department of Computer Science, Georgia State University, University Plaza, 30303-3083, Atlanta, GA, USA
119 rdf:type schema:Organization
120 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Penn State University, 16802, University Park, PA, USA
121 schema:name Department of Computer Science and Engineering, Penn State University, 16802, University Park, PA, USA
122 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...