An upper bound for the speedup of parallel best-bound branch-and-bound algorithms View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1986-03

AUTHORS

Michael J. Quinn, Narsingh Deo

ABSTRACT

This paper derives an upper bound for the speedup obtainable by any parallel branch-and-bound algorithm using the best-bound search strategy. We confirm that parallel branch-and-bound can achieve nearly linear, or even super-linear, speedup under the appropriate conditions.

PAGES

35-43

References to SciGraph publications

  • 1976-12. Theoretical comparisons of search strategies in branch-and-bound algorithms in INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
  • 1971-12. The traveling-salesman problem and minimum spanning trees: Part II in MATHEMATICAL PROGRAMMING
  • Journal

    TITLE

    BIT Numerical Mathematics

    ISSUE

    1

    VOLUME

    26

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01939360

    DOI

    http://dx.doi.org/10.1007/bf01939360

    DIMENSIONS

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


    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", 
        "author": [
          {
            "affiliation": {
              "alternateName": "Washington State University", 
              "id": "https://www.grid.ac/institutes/grid.30064.31", 
              "name": [
                "Department of Computer Science, University of New Hampshire, 03824, Durham, New Hampshire, USA", 
                "Computer Science Department, Washington State University, 99164, Pullman, Washington, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Quinn", 
            "givenName": "Michael J.", 
            "id": "sg:person.016211427445.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016211427445.02"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Washington State University", 
              "id": "https://www.grid.ac/institutes/grid.30064.31", 
              "name": [
                "Department of Computer Science, University of New Hampshire, 03824, Durham, New Hampshire, USA", 
                "Computer Science Department, Washington State University, 99164, Pullman, Washington, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deo", 
            "givenName": "Narsingh", 
            "id": "sg:person.010274011142.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1002/nav.3800180102", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030857196"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01584070", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044774302", 
              "https://doi.org/10.1007/bf01584070"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00998631", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052307646", 
              "https://doi.org/10.1007/bf00998631"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/mnsc.18.9.465", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064717041"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.11.6.972", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064726361"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.13.3.400", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064726861"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.18.2.263", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064727444"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.20.3.668", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064727799"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1986-03", 
        "datePublishedReg": "1986-03-01", 
        "description": "This paper derives an upper bound for the speedup obtainable by any parallel branch-and-bound algorithm using the best-bound search strategy. We confirm that parallel branch-and-bound can achieve nearly linear, or even super-linear, speedup under the appropriate conditions.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01939360", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136252", 
            "issn": [
              "0006-3835", 
              "1572-9125"
            ], 
            "name": "BIT Numerical Mathematics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "26"
          }
        ], 
        "name": "An upper bound for the speedup of parallel best-bound branch-and-bound algorithms", 
        "pagination": "35-43", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "691e4d1bb5e5ce23a58012347d4ce11eea4023161e92a2fcd7b7c1156daba43b"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01939360"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1022063860"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01939360", 
          "https://app.dimensions.ai/details/publication/pub.1022063860"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:14", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000353_0000000353/records_45376_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF01939360"
      }
    ]
     

    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/bf01939360'

    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/bf01939360'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01939360'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01939360'


     

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

    87 TRIPLES      20 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01939360 schema:author N8880c1dabb03463b9537323cc22437da
    2 schema:citation sg:pub.10.1007/bf00998631
    3 sg:pub.10.1007/bf01584070
    4 https://doi.org/10.1002/nav.3800180102
    5 https://doi.org/10.1287/mnsc.18.9.465
    6 https://doi.org/10.1287/opre.11.6.972
    7 https://doi.org/10.1287/opre.13.3.400
    8 https://doi.org/10.1287/opre.18.2.263
    9 https://doi.org/10.1287/opre.20.3.668
    10 schema:datePublished 1986-03
    11 schema:datePublishedReg 1986-03-01
    12 schema:description This paper derives an upper bound for the speedup obtainable by any parallel branch-and-bound algorithm using the best-bound search strategy. We confirm that parallel branch-and-bound can achieve nearly linear, or even super-linear, speedup under the appropriate conditions.
    13 schema:genre research_article
    14 schema:inLanguage en
    15 schema:isAccessibleForFree false
    16 schema:isPartOf N31252fbb02b442318082f6c8d233cf3b
    17 Nc5380a8cdece4fdda585b684bb600184
    18 sg:journal.1136252
    19 schema:name An upper bound for the speedup of parallel best-bound branch-and-bound algorithms
    20 schema:pagination 35-43
    21 schema:productId N75cc1f13e40c46d8b0db3b3da5c03e81
    22 Nabb1e3780a34402cbb8e915d6f173ed4
    23 Nd0842c629de04ecfa133286a030d7615
    24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022063860
    25 https://doi.org/10.1007/bf01939360
    26 schema:sdDatePublished 2019-04-11T11:14
    27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    28 schema:sdPublisher N9450cdcecd4041f1b1eefa1988642648
    29 schema:url http://link.springer.com/10.1007/BF01939360
    30 sgo:license sg:explorer/license/
    31 sgo:sdDataset articles
    32 rdf:type schema:ScholarlyArticle
    33 N31252fbb02b442318082f6c8d233cf3b schema:issueNumber 1
    34 rdf:type schema:PublicationIssue
    35 N57b0a58b7b73459492b6cbc9527e208c rdf:first sg:person.010274011142.47
    36 rdf:rest rdf:nil
    37 N75cc1f13e40c46d8b0db3b3da5c03e81 schema:name dimensions_id
    38 schema:value pub.1022063860
    39 rdf:type schema:PropertyValue
    40 N8880c1dabb03463b9537323cc22437da rdf:first sg:person.016211427445.02
    41 rdf:rest N57b0a58b7b73459492b6cbc9527e208c
    42 N9450cdcecd4041f1b1eefa1988642648 schema:name Springer Nature - SN SciGraph project
    43 rdf:type schema:Organization
    44 Nabb1e3780a34402cbb8e915d6f173ed4 schema:name readcube_id
    45 schema:value 691e4d1bb5e5ce23a58012347d4ce11eea4023161e92a2fcd7b7c1156daba43b
    46 rdf:type schema:PropertyValue
    47 Nc5380a8cdece4fdda585b684bb600184 schema:volumeNumber 26
    48 rdf:type schema:PublicationVolume
    49 Nd0842c629de04ecfa133286a030d7615 schema:name doi
    50 schema:value 10.1007/bf01939360
    51 rdf:type schema:PropertyValue
    52 sg:journal.1136252 schema:issn 0006-3835
    53 1572-9125
    54 schema:name BIT Numerical Mathematics
    55 rdf:type schema:Periodical
    56 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.30064.31
    57 schema:familyName Deo
    58 schema:givenName Narsingh
    59 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
    60 rdf:type schema:Person
    61 sg:person.016211427445.02 schema:affiliation https://www.grid.ac/institutes/grid.30064.31
    62 schema:familyName Quinn
    63 schema:givenName Michael J.
    64 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016211427445.02
    65 rdf:type schema:Person
    66 sg:pub.10.1007/bf00998631 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052307646
    67 https://doi.org/10.1007/bf00998631
    68 rdf:type schema:CreativeWork
    69 sg:pub.10.1007/bf01584070 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044774302
    70 https://doi.org/10.1007/bf01584070
    71 rdf:type schema:CreativeWork
    72 https://doi.org/10.1002/nav.3800180102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030857196
    73 rdf:type schema:CreativeWork
    74 https://doi.org/10.1287/mnsc.18.9.465 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064717041
    75 rdf:type schema:CreativeWork
    76 https://doi.org/10.1287/opre.11.6.972 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064726361
    77 rdf:type schema:CreativeWork
    78 https://doi.org/10.1287/opre.13.3.400 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064726861
    79 rdf:type schema:CreativeWork
    80 https://doi.org/10.1287/opre.18.2.263 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064727444
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1287/opre.20.3.668 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064727799
    83 rdf:type schema:CreativeWork
    84 https://www.grid.ac/institutes/grid.30064.31 schema:alternateName Washington State University
    85 schema:name Computer Science Department, Washington State University, 99164, Pullman, Washington, USA
    86 Department of Computer Science, University of New Hampshire, 03824, Durham, New Hampshire, USA
    87 rdf:type schema:Organization
     




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


    ...