Polynomial Time Approximation Scheme for Symmetric Rectilinear Steiner Arborescence Problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2001-12

AUTHORS

Xiuzhen Cheng, Bhaskar DasGupta, Bing Lu

ABSTRACT

The Symmetric Rectilinear Steiner Arborescence (SRStA) problem is defined as follows: given a set of terminals in the positive quadrant of the plane, connect them using horizontal and vertical lines such that each terminal can be reached from the origin via a y-monotone path and the total length of all the line segments is the minimum possible. Finding an SRStA has applications in VLSI design, in data structures used in some optimization algorithms and in dynamic server problems. In this paper, we provide a polynomial time approximation scheme for the SRStA problem, improving the previous best approximation ratio of 3 for this problem. More... »

PAGES

385-396

References to SciGraph publications

  • 1985-05. Subclass of the Steiner problems on a plane with rectilinear metric in CYBERNETICS AND SYSTEMS ANALYSIS
  • 1995. Optimal information delivery in ALGORITHMS AND COMPUTATIONS
  • 1992-06. The rectilinear steiner arborescence problem in ALGORITHMICA
  • 2000-09. Polynomial Time Approximation Scheme for the Rectilinear Steiner Arborescence Problem in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1012730702524

    DOI

    http://dx.doi.org/10.1023/a:1012730702524

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA", 
              "id": "http://www.grid.ac/institutes/grid.17635.36", 
              "name": [
                "Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cheng", 
            "givenName": "Xiuzhen", 
            "id": "sg:person.01010535264.21", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01010535264.21"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Rutgers University campus at Camden, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Rutgers University campus at Camden, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "DasGupta", 
            "givenName": "Bhaskar", 
            "id": "sg:person.0763403270.10", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA", 
              "id": "http://www.grid.ac/institutes/grid.17635.36", 
              "name": [
                "Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lu", 
            "givenName": "Bing", 
            "id": "sg:person.013702360446.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013702360446.01"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bfb0015422", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019316231", 
              "https://doi.org/10.1007/bfb0015422"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01078826", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052877272", 
              "https://doi.org/10.1007/bf01078826"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1009826311973", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033463750", 
              "https://doi.org/10.1023/a:1009826311973"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01758762", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046029487", 
              "https://doi.org/10.1007/bf01758762"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2001-12", 
        "datePublishedReg": "2001-12-01", 
        "description": "The Symmetric Rectilinear Steiner Arborescence (SRStA) problem is defined as follows: given a set of terminals in the positive quadrant of the plane, connect them using horizontal and vertical lines such that each terminal can be reached from the origin via a y-monotone path and the total length of all the line segments is the minimum possible. Finding an SRStA has applications in VLSI design, in data structures used in some optimization algorithms and in dynamic server problems. In this paper, we provide a polynomial time approximation scheme for the SRStA problem, improving the previous best approximation ratio of 3 for this problem.", 
        "genre": "article", 
        "id": "sg:pub.10.1023/a:1012730702524", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1050312", 
            "issn": [
              "0925-5001", 
              "1573-2916"
            ], 
            "name": "Journal of Global Optimization", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "21"
          }
        ], 
        "keywords": [
          "polynomial time approximation scheme", 
          "time approximation scheme", 
          "rectilinear Steiner arborescence problem", 
          "Steiner arborescence problem", 
          "arborescence problem", 
          "data structure", 
          "server problem", 
          "best approximation ratio", 
          "approximation scheme", 
          "set of terminals", 
          "approximation ratio", 
          "optimization algorithm", 
          "VLSI design", 
          "line segments", 
          "scheme", 
          "algorithm", 
          "positive quadrant", 
          "monotone path", 
          "terminals", 
          "set", 
          "vertical line", 
          "applications", 
          "path", 
          "previous best approximation ratio", 
          "design", 
          "problem", 
          "plane", 
          "segments", 
          "minimum", 
          "structure", 
          "lines", 
          "length", 
          "ratio", 
          "total length", 
          "origin", 
          "quadrant", 
          "paper"
        ], 
        "name": "Polynomial Time Approximation Scheme for Symmetric Rectilinear Steiner Arborescence Problem", 
        "pagination": "385-396", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1000290247"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1012730702524"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1012730702524", 
          "https://app.dimensions.ai/details/publication/pub.1000290247"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:21", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_335.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1023/a:1012730702524"
      }
    ]
     

    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.1023/a:1012730702524'

    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.1023/a:1012730702524'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1012730702524'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1012730702524'


     

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

    128 TRIPLES      22 PREDICATES      67 URIs      55 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1012730702524 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N1477c6fc7c9241edab9ba1fe787fd6e2
    4 schema:citation sg:pub.10.1007/bf01078826
    5 sg:pub.10.1007/bf01758762
    6 sg:pub.10.1007/bfb0015422
    7 sg:pub.10.1023/a:1009826311973
    8 schema:datePublished 2001-12
    9 schema:datePublishedReg 2001-12-01
    10 schema:description The Symmetric Rectilinear Steiner Arborescence (SRStA) problem is defined as follows: given a set of terminals in the positive quadrant of the plane, connect them using horizontal and vertical lines such that each terminal can be reached from the origin via a y-monotone path and the total length of all the line segments is the minimum possible. Finding an SRStA has applications in VLSI design, in data structures used in some optimization algorithms and in dynamic server problems. In this paper, we provide a polynomial time approximation scheme for the SRStA problem, improving the previous best approximation ratio of 3 for this problem.
    11 schema:genre article
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf N40dc93361f9d43728f1d95d3fac8c557
    15 Naa2b87f8dd7f4a8eb1880624dc02f437
    16 sg:journal.1050312
    17 schema:keywords Steiner arborescence problem
    18 VLSI design
    19 algorithm
    20 applications
    21 approximation ratio
    22 approximation scheme
    23 arborescence problem
    24 best approximation ratio
    25 data structure
    26 design
    27 length
    28 line segments
    29 lines
    30 minimum
    31 monotone path
    32 optimization algorithm
    33 origin
    34 paper
    35 path
    36 plane
    37 polynomial time approximation scheme
    38 positive quadrant
    39 previous best approximation ratio
    40 problem
    41 quadrant
    42 ratio
    43 rectilinear Steiner arborescence problem
    44 scheme
    45 segments
    46 server problem
    47 set
    48 set of terminals
    49 structure
    50 terminals
    51 time approximation scheme
    52 total length
    53 vertical line
    54 schema:name Polynomial Time Approximation Scheme for Symmetric Rectilinear Steiner Arborescence Problem
    55 schema:pagination 385-396
    56 schema:productId N4dd59b84844c4c89bd4304454d89fbac
    57 Nd384fe3cffe54dcdbad210dc40367782
    58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000290247
    59 https://doi.org/10.1023/a:1012730702524
    60 schema:sdDatePublished 2022-05-20T07:21
    61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    62 schema:sdPublisher N3b9103a1a7a444d0b827b38675102e6d
    63 schema:url https://doi.org/10.1023/a:1012730702524
    64 sgo:license sg:explorer/license/
    65 sgo:sdDataset articles
    66 rdf:type schema:ScholarlyArticle
    67 N1477c6fc7c9241edab9ba1fe787fd6e2 rdf:first sg:person.01010535264.21
    68 rdf:rest Nfea165a23ac04358b2f9319a3197b5fc
    69 N174a005b73b249279373a035d224294b rdf:first sg:person.013702360446.01
    70 rdf:rest rdf:nil
    71 N3b9103a1a7a444d0b827b38675102e6d schema:name Springer Nature - SN SciGraph project
    72 rdf:type schema:Organization
    73 N40dc93361f9d43728f1d95d3fac8c557 schema:volumeNumber 21
    74 rdf:type schema:PublicationVolume
    75 N4dd59b84844c4c89bd4304454d89fbac schema:name doi
    76 schema:value 10.1023/a:1012730702524
    77 rdf:type schema:PropertyValue
    78 Naa2b87f8dd7f4a8eb1880624dc02f437 schema:issueNumber 4
    79 rdf:type schema:PublicationIssue
    80 Nd384fe3cffe54dcdbad210dc40367782 schema:name dimensions_id
    81 schema:value pub.1000290247
    82 rdf:type schema:PropertyValue
    83 Nfea165a23ac04358b2f9319a3197b5fc rdf:first sg:person.0763403270.10
    84 rdf:rest N174a005b73b249279373a035d224294b
    85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Information and Computing Sciences
    87 rdf:type schema:DefinedTerm
    88 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Computation Theory and Mathematics
    90 rdf:type schema:DefinedTerm
    91 sg:journal.1050312 schema:issn 0925-5001
    92 1573-2916
    93 schema:name Journal of Global Optimization
    94 schema:publisher Springer Nature
    95 rdf:type schema:Periodical
    96 sg:person.01010535264.21 schema:affiliation grid-institutes:grid.17635.36
    97 schema:familyName Cheng
    98 schema:givenName Xiuzhen
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01010535264.21
    100 rdf:type schema:Person
    101 sg:person.013702360446.01 schema:affiliation grid-institutes:grid.17635.36
    102 schema:familyName Lu
    103 schema:givenName Bing
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013702360446.01
    105 rdf:type schema:Person
    106 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.430387.b
    107 schema:familyName DasGupta
    108 schema:givenName Bhaskar
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
    110 rdf:type schema:Person
    111 sg:pub.10.1007/bf01078826 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052877272
    112 https://doi.org/10.1007/bf01078826
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/bf01758762 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046029487
    115 https://doi.org/10.1007/bf01758762
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/bfb0015422 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019316231
    118 https://doi.org/10.1007/bfb0015422
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1023/a:1009826311973 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033463750
    121 https://doi.org/10.1023/a:1009826311973
    122 rdf:type schema:CreativeWork
    123 grid-institutes:grid.17635.36 schema:alternateName Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA
    124 schema:name Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA
    125 rdf:type schema:Organization
    126 grid-institutes:grid.430387.b schema:alternateName Rutgers University campus at Camden, USA
    127 schema:name Rutgers University campus at Camden, USA
    128 rdf:type schema:Organization
     




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


    ...