Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2005-03-02

AUTHORS

Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky

ABSTRACT

The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the source to non-zero rate nodes is l · re, where re is the maximum node rate in the component of T-{e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.212 for the case of an unbounded number of rates. In this paper we give improved approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for an unbounded number of rates are reduced to 2.414 and 4.311, respectively. More... »

PAGES

109-120

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-004-1133-y

DOI

http://dx.doi.org/10.1007/s00453-004-1133-y

DIMENSIONS

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


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/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Communications Technologies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Bonn, Bonn 53117, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Department of Computer Science, University of Bonn, Bonn 53117, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Rd., Unit 2155,\nStorrs, CT 06269-2155, USA", 
          "id": "http://www.grid.ac/institutes/grid.63054.34", 
          "name": [
            "Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Rd., Unit 2155,\nStorrs, CT 06269-2155, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mandoiu", 
        "givenName": "Ion I.", 
        "id": "sg:person.01017610620.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01017610620.16"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Boston,\nMA 02139-4307, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Boston,\nMA 02139-4307, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Olshevsky", 
        "givenName": "Alexander", 
        "id": "sg:person.0765153202.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0765153202.58"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, Georgia State University, Atlanta, GA 30303,, USA", 
          "id": "http://www.grid.ac/institutes/grid.256304.6", 
          "name": [
            "Computer Science Department, Georgia State University, Atlanta, GA 30303,, 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": "2005-03-02", 
    "datePublishedReg": "2005-03-02", 
    "description": "Abstract\nThe Quality of Service Multicast Tree Problem is a generalization of\nthe Steiner tree problem which appears in the context of multimedia\nmulticast and network design. In this generalization, each node\npossesses a rate and the cost of an edge with length l in a\nSteiner tree T connecting the source to non-zero rate nodes is l\n\u00b7 re, where re is the maximum node rate in the component of\nT-{e} that does not contain the source. The best previously\nknown approximation ratios for this problem (based on the best known\napproximation factor of 1.549 for the Steiner tree problem in\nnetworks) are 2.066 for the case of two non-zero rates and 4.212 for\nthe case of an unbounded number of rates. In this paper we give\nimproved approximation algorithms with ratios of 1.960 and 3.802,\nrespectively. When the minimum spanning tree heuristic is used for\nfinding approximate Steiner trees, then the previously best known\napproximation ratios of 2.667 for two non-zero rates and 5.542 for an\nunbounded number of rates are reduced to 2.414 and 4.311,\nrespectively.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-004-1133-y", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "42"
      }
    ], 
    "keywords": [
      "multicast tree problem", 
      "unbounded number", 
      "tree problem", 
      "context of multimedia", 
      "approximation algorithm", 
      "approximation ratio", 
      "Steiner tree problem", 
      "improved approximation algorithms", 
      "network design", 
      "minimum spanning tree heuristic", 
      "non-zero rates", 
      "tree heuristic", 
      "Steiner tree", 
      "algorithm", 
      "approximate Steiner tree", 
      "nodes", 
      "multimedia", 
      "multicast", 
      "heuristics", 
      "quality", 
      "generalization", 
      "node rate", 
      "tree T", 
      "cost", 
      "trees", 
      "design", 
      "number", 
      "edge", 
      "context", 
      "source", 
      "components", 
      "cases", 
      "Steiner tree T", 
      "rate", 
      "Re", 
      "ratio", 
      "length", 
      "problem", 
      "paper"
    ], 
    "name": "Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem", 
    "pagination": "109-120", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043048301"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-004-1133-y"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-004-1133-y", 
      "https://app.dimensions.ai/details/publication/pub.1043048301"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-12-01T06:25", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_395.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-004-1133-y"
  }
]
 

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/s00453-004-1133-y'

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/s00453-004-1133-y'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-004-1133-y'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-004-1133-y'


 

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

126 TRIPLES      20 PREDICATES      63 URIs      55 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-004-1133-y schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author Nd668e9adc4634139a373e10aeca282cf
4 schema:datePublished 2005-03-02
5 schema:datePublishedReg 2005-03-02
6 schema:description Abstract The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the source to non-zero rate nodes is l · re, where re is the maximum node rate in the component of T-{e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.212 for the case of an unbounded number of rates. In this paper we give improved approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for an unbounded number of rates are reduced to 2.414 and 4.311, respectively.
7 schema:genre article
8 schema:isAccessibleForFree false
9 schema:isPartOf N1b5cd648ab4245b09e3b83d97d69e7a9
10 N528d7e5b69704b8a926f0d542b1a760d
11 sg:journal.1047644
12 schema:keywords Re
13 Steiner tree
14 Steiner tree T
15 Steiner tree problem
16 algorithm
17 approximate Steiner tree
18 approximation algorithm
19 approximation ratio
20 cases
21 components
22 context
23 context of multimedia
24 cost
25 design
26 edge
27 generalization
28 heuristics
29 improved approximation algorithms
30 length
31 minimum spanning tree heuristic
32 multicast
33 multicast tree problem
34 multimedia
35 network design
36 node rate
37 nodes
38 non-zero rates
39 number
40 paper
41 problem
42 quality
43 rate
44 ratio
45 source
46 tree T
47 tree heuristic
48 tree problem
49 trees
50 unbounded number
51 schema:name Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem
52 schema:pagination 109-120
53 schema:productId N85145c81b63c4a9f943012649b3ff822
54 N967588909e3c425a8a899ec0fbffb008
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043048301
56 https://doi.org/10.1007/s00453-004-1133-y
57 schema:sdDatePublished 2022-12-01T06:25
58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
59 schema:sdPublisher N4968ad79ac1145b6b35eeb6edb2f8199
60 schema:url https://doi.org/10.1007/s00453-004-1133-y
61 sgo:license sg:explorer/license/
62 sgo:sdDataset articles
63 rdf:type schema:ScholarlyArticle
64 N1b5cd648ab4245b09e3b83d97d69e7a9 schema:issueNumber 2
65 rdf:type schema:PublicationIssue
66 N4968ad79ac1145b6b35eeb6edb2f8199 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N528d7e5b69704b8a926f0d542b1a760d schema:volumeNumber 42
69 rdf:type schema:PublicationVolume
70 N85145c81b63c4a9f943012649b3ff822 schema:name doi
71 schema:value 10.1007/s00453-004-1133-y
72 rdf:type schema:PropertyValue
73 N967588909e3c425a8a899ec0fbffb008 schema:name dimensions_id
74 schema:value pub.1043048301
75 rdf:type schema:PropertyValue
76 N97b092519e4e4b11852a5fd5afc3f097 rdf:first sg:person.01017610620.16
77 rdf:rest Ne7b8ece058244171b495e9b3b7ad3530
78 Nd668e9adc4634139a373e10aeca282cf rdf:first sg:person.011636042271.02
79 rdf:rest N97b092519e4e4b11852a5fd5afc3f097
80 Ne51de74fda0b4d13b6d2cd75d89f8e69 rdf:first sg:person.01121041073.51
81 rdf:rest rdf:nil
82 Ne7b8ece058244171b495e9b3b7ad3530 rdf:first sg:person.0765153202.58
83 rdf:rest Ne51de74fda0b4d13b6d2cd75d89f8e69
84 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
85 schema:name Technology
86 rdf:type schema:DefinedTerm
87 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
88 schema:name Communications Technologies
89 rdf:type schema:DefinedTerm
90 sg:journal.1047644 schema:issn 0178-4617
91 1432-0541
92 schema:name Algorithmica
93 schema:publisher Springer Nature
94 rdf:type schema:Periodical
95 sg:person.01017610620.16 schema:affiliation grid-institutes:grid.63054.34
96 schema:familyName Mandoiu
97 schema:givenName Ion I.
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01017610620.16
99 rdf:type schema:Person
100 sg:person.01121041073.51 schema:affiliation grid-institutes:grid.256304.6
101 schema:familyName Zelikovsky
102 schema:givenName Alexander
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01121041073.51
104 rdf:type schema:Person
105 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
106 schema:familyName Karpinski
107 schema:givenName Marek
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
109 rdf:type schema:Person
110 sg:person.0765153202.58 schema:affiliation grid-institutes:grid.116068.8
111 schema:familyName Olshevsky
112 schema:givenName Alexander
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0765153202.58
114 rdf:type schema:Person
115 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn, Bonn 53117, Germany
116 schema:name Department of Computer Science, University of Bonn, Bonn 53117, Germany
117 rdf:type schema:Organization
118 grid-institutes:grid.116068.8 schema:alternateName Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Boston, MA 02139-4307, USA
119 schema:name Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Boston, MA 02139-4307, USA
120 rdf:type schema:Organization
121 grid-institutes:grid.256304.6 schema:alternateName Computer Science Department, Georgia State University, Atlanta, GA 30303,, USA
122 schema:name Computer Science Department, Georgia State University, Atlanta, GA 30303,, USA
123 rdf:type schema:Organization
124 grid-institutes:grid.63054.34 schema:alternateName Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Rd., Unit 2155, Storrs, CT 06269-2155, USA
125 schema:name Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Rd., Unit 2155, Storrs, CT 06269-2155, USA
126 rdf:type schema:Organization
 




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


...