The searching over separators strategy to solve some NP-hard problems in subexponential time View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-04

AUTHORS

R. Z. Hwang, R. C. Chang, R. C. T. Lee

ABSTRACT

In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts,Ad andCd, in such a way that after solving these two subproblems withAd andCd as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete EuclideanP-median problem (DEPM), the discrete EuclideanP-center problem (DEPC), the EuclideanP-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(n^{o(\sqrt P )} )$$ \end{document} algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(n^{o(\sqrt n )} )$$ \end{document} algorithm for the ETSP problem, wheren is the number of input points. More... »

PAGES

398-423

References to SciGraph publications

  • 1987. Algorithms in Combinatorial Geometry in NONE
  • 1984-08-01. The p-Centre Problem—Heuristic and Optimal Algorithms in JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • 1985. Computational Geometry, An Introduction in NONE
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China", 
              "id": "http://www.grid.ac/institutes/grid.38348.34", 
              "name": [
                "Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hwang", 
            "givenName": "R. Z.", 
            "id": "sg:person.014072526441.41", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014072526441.41"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Academia Sinica, Hsinchu, Taiwan, Republic of China", 
              "id": "http://www.grid.ac/institutes/grid.28665.3f", 
              "name": [
                "Institute of Computer Science, National Chiao Tung University, Hsinchu, Taiwan, Republic of China", 
                "Academia Sinica, Hsinchu, Taiwan, Republic of China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chang", 
            "givenName": "R. C.", 
            "id": "sg:person.012355347703.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012355347703.02"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Academia Sinica, Hsinchu, Taiwan, Republic of China", 
              "id": "http://www.grid.ac/institutes/grid.28665.3f", 
              "name": [
                "Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China", 
                "Academia Sinica, Hsinchu, Taiwan, Republic of China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lee", 
            "givenName": "R. C. T.", 
            "id": "sg:person.07540250215.50", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1057/jors.1984.150", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029954112", 
              "https://doi.org/10.1057/jors.1984.150"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-1098-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021021236", 
              "https://doi.org/10.1007/978-1-4612-1098-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-61568-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049996833", 
              "https://doi.org/10.1007/978-3-642-61568-9"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1993-04", 
        "datePublishedReg": "1993-04-01", 
        "description": "In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts,Ad andCd, in such a way that after solving these two subproblems withAd andCd as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete EuclideanP-median problem (DEPM), the discrete EuclideanP-center problem (DEPC), the EuclideanP-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$O(n^{o(\\sqrt P )} )$$\n\\end{document} algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$O(n^{o(\\sqrt n )} )$$\n\\end{document} algorithm for the ETSP problem, wheren is the number of input points.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01228511", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "9"
          }
        ], 
        "keywords": [
          "optimal solution", 
          "separator", 
          "generator", 
          "solution", 
          "optimization problem", 
          "performance", 
          "new strategy", 
          "strategies", 
          "algorithm", 
          "problem", 
          "input points", 
          "point", 
          "input", 
          "approach", 
          "total number", 
          "part", 
          "way", 
          "cases", 
          "number", 
          "NP-hard problem", 
          "time", 
          "searching", 
          "conquer strategy", 
          "wheren", 
          "paper", 
          "divide", 
          "subsolutions", 
          "Euclidean", 
          "salesperson problem", 
          "subexponential time", 
          "separators strategy", 
          "Ad andCd", 
          "andCd", 
          "subproblems withAd andCd", 
          "withAd andCd", 
          "respective subsolutions", 
          "separator generator", 
          "possible separators", 
          "discrete EuclideanP-median problem", 
          "EuclideanP-median problem", 
          "discrete EuclideanP-center problem", 
          "EuclideanP-center problem", 
          "DEPM problem", 
          "DEPC problem", 
          "EPC problem", 
          "ETSP problem"
        ], 
        "name": "The searching over separators strategy to solve some NP-hard problems in subexponential time", 
        "pagination": "398-423", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1006480954"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01228511"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01228511", 
          "https://app.dimensions.ai/details/publication/pub.1006480954"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:07", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_223.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01228511"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    135 TRIPLES      22 PREDICATES      75 URIs      64 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01228511 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author N1f917a93ae93495cabe9f92bcb49519b
    4 schema:citation sg:pub.10.1007/978-1-4612-1098-6
    5 sg:pub.10.1007/978-3-642-61568-9
    6 sg:pub.10.1057/jors.1984.150
    7 schema:datePublished 1993-04
    8 schema:datePublishedReg 1993-04-01
    9 schema:description In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts,Ad andCd, in such a way that after solving these two subproblems withAd andCd as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete EuclideanP-median problem (DEPM), the discrete EuclideanP-center problem (DEPC), the EuclideanP-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(n^{o(\sqrt P )} )$$ \end{document} algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(n^{o(\sqrt n )} )$$ \end{document} algorithm for the ETSP problem, wheren is the number of input points.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N2cd274150aa74ae586511e07938ba744
    14 N706e09ff134649f1a8b579ea1d219c09
    15 sg:journal.1047644
    16 schema:keywords Ad andCd
    17 DEPC problem
    18 DEPM problem
    19 EPC problem
    20 ETSP problem
    21 Euclidean
    22 EuclideanP-center problem
    23 EuclideanP-median problem
    24 NP-hard problem
    25 algorithm
    26 andCd
    27 approach
    28 cases
    29 conquer strategy
    30 discrete EuclideanP-center problem
    31 discrete EuclideanP-median problem
    32 divide
    33 generator
    34 input
    35 input points
    36 new strategy
    37 number
    38 optimal solution
    39 optimization problem
    40 paper
    41 part
    42 performance
    43 point
    44 possible separators
    45 problem
    46 respective subsolutions
    47 salesperson problem
    48 searching
    49 separator
    50 separator generator
    51 separators strategy
    52 solution
    53 strategies
    54 subexponential time
    55 subproblems withAd andCd
    56 subsolutions
    57 time
    58 total number
    59 way
    60 wheren
    61 withAd andCd
    62 schema:name The searching over separators strategy to solve some NP-hard problems in subexponential time
    63 schema:pagination 398-423
    64 schema:productId N95798090aaad47fcab9679c6035c157e
    65 Naeecc6181c774aeeb69cfff6b201a805
    66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006480954
    67 https://doi.org/10.1007/bf01228511
    68 schema:sdDatePublished 2021-12-01T19:07
    69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    70 schema:sdPublisher N35fe572342534e579f766a92099a01ea
    71 schema:url https://doi.org/10.1007/bf01228511
    72 sgo:license sg:explorer/license/
    73 sgo:sdDataset articles
    74 rdf:type schema:ScholarlyArticle
    75 N1f917a93ae93495cabe9f92bcb49519b rdf:first sg:person.014072526441.41
    76 rdf:rest Ned64d743864e4545995a1e8de9a83fff
    77 N2cd274150aa74ae586511e07938ba744 schema:volumeNumber 9
    78 rdf:type schema:PublicationVolume
    79 N35fe572342534e579f766a92099a01ea schema:name Springer Nature - SN SciGraph project
    80 rdf:type schema:Organization
    81 N671e53343b554b64a9e837b32d2321dc rdf:first sg:person.07540250215.50
    82 rdf:rest rdf:nil
    83 N706e09ff134649f1a8b579ea1d219c09 schema:issueNumber 4
    84 rdf:type schema:PublicationIssue
    85 N95798090aaad47fcab9679c6035c157e schema:name dimensions_id
    86 schema:value pub.1006480954
    87 rdf:type schema:PropertyValue
    88 Naeecc6181c774aeeb69cfff6b201a805 schema:name doi
    89 schema:value 10.1007/bf01228511
    90 rdf:type schema:PropertyValue
    91 Ned64d743864e4545995a1e8de9a83fff rdf:first sg:person.012355347703.02
    92 rdf:rest N671e53343b554b64a9e837b32d2321dc
    93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Information and Computing Sciences
    95 rdf:type schema:DefinedTerm
    96 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    97 schema:name Data Format
    98 rdf:type schema:DefinedTerm
    99 sg:journal.1047644 schema:issn 0178-4617
    100 1432-0541
    101 schema:name Algorithmica
    102 schema:publisher Springer Nature
    103 rdf:type schema:Periodical
    104 sg:person.012355347703.02 schema:affiliation grid-institutes:grid.28665.3f
    105 schema:familyName Chang
    106 schema:givenName R. C.
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012355347703.02
    108 rdf:type schema:Person
    109 sg:person.014072526441.41 schema:affiliation grid-institutes:grid.38348.34
    110 schema:familyName Hwang
    111 schema:givenName R. Z.
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014072526441.41
    113 rdf:type schema:Person
    114 sg:person.07540250215.50 schema:affiliation grid-institutes:grid.28665.3f
    115 schema:familyName Lee
    116 schema:givenName R. C. T.
    117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50
    118 rdf:type schema:Person
    119 sg:pub.10.1007/978-1-4612-1098-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021021236
    120 https://doi.org/10.1007/978-1-4612-1098-6
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-3-642-61568-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049996833
    123 https://doi.org/10.1007/978-3-642-61568-9
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1057/jors.1984.150 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029954112
    126 https://doi.org/10.1057/jors.1984.150
    127 rdf:type schema:CreativeWork
    128 grid-institutes:grid.28665.3f schema:alternateName Academia Sinica, Hsinchu, Taiwan, Republic of China
    129 schema:name Academia Sinica, Hsinchu, Taiwan, Republic of China
    130 Institute of Computer Science, National Chiao Tung University, Hsinchu, Taiwan, Republic of China
    131 Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China
    132 rdf:type schema:Organization
    133 grid-institutes:grid.38348.34 schema:alternateName Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China
    134 schema:name Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China
    135 rdf:type schema:Organization
     




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


    ...