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-10-01T06:53", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_164.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 Ne8f9158595e947daa42db5483ef35248
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 Ne0d3fcd5a13349e3a5e59aa404627998
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N4f8ed02e3b54481db7b958c7ee482c4b
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 N1eb0b186c9744b148a3952a526c4d5c6
57 Nffbeb9f9b49342f897def140c8686d2b
58 schema:publisher N46ba6805daf24f42a6fe0fbb0012568d
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-10-01T06:53
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher Nfe8d090ed0ca4709a2c41e34623cfa88
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 N1eb0b186c9744b148a3952a526c4d5c6 schema:name dimensions_id
69 schema:value pub.1035699208
70 rdf:type schema:PropertyValue
71 N3321db08a63e4d42b5a2f62938c6f3f5 schema:familyName Rubinstein
72 schema:givenName J. H.
73 rdf:type schema:Person
74 N46ba6805daf24f42a6fe0fbb0012568d schema:name Springer Nature
75 rdf:type schema:Organisation
76 N4f8ed02e3b54481db7b958c7ee482c4b schema:isbn 978-1-4419-4824-3
77 978-1-4757-3171-2
78 schema:name Advances in Steiner Trees
79 rdf:type schema:Book
80 N7f43667a4c5e4cf6acc197ba170c8fd6 rdf:first sg:person.01121041073.51
81 rdf:rest rdf:nil
82 Ncbd23020423d42ec858456e19e4a5e69 schema:familyName Du
83 schema:givenName Ding-Zhu
84 rdf:type schema:Person
85 Ncee594c4e8f2467691f6747c5cd66c6e schema:familyName Smith
86 schema:givenName J. M.
87 rdf:type schema:Person
88 Ne0d3fcd5a13349e3a5e59aa404627998 rdf:first Ncbd23020423d42ec858456e19e4a5e69
89 rdf:rest Nf8e0b51682a54880adef2f0a163e3c91
90 Ne15f53c7dd2f4d8eb086a873ffb6b8e6 rdf:first N3321db08a63e4d42b5a2f62938c6f3f5
91 rdf:rest rdf:nil
92 Ne8f9158595e947daa42db5483ef35248 rdf:first sg:person.01274506210.27
93 rdf:rest N7f43667a4c5e4cf6acc197ba170c8fd6
94 Nf8e0b51682a54880adef2f0a163e3c91 rdf:first Ncee594c4e8f2467691f6747c5cd66c6e
95 rdf:rest Ne15f53c7dd2f4d8eb086a873ffb6b8e6
96 Nfe8d090ed0ca4709a2c41e34623cfa88 schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 Nffbeb9f9b49342f897def140c8686d2b schema:name doi
99 schema:value 10.1007/978-1-4757-3171-2_7
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)


...