An efficient heuristic algorithm for minimum matching View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1990-07

AUTHORS

P. Grassberger, H. Freund

ABSTRACT

We give a new heuristic algorithm for minimum matching problems and apply it to the Euclidean problem with random vertices in 2 dimensions. The algorithm is based on simulated annealing and performs in practice faster than previous heuristic algorithms yielding suboptimal solutions of the same good quality. From configurations with up toN=20.000 vertices in the unit square we estimate that the length of a minimum matching scales asymptotically asL∼Β√N with (Β=0.3123±0.0016. More... »

PAGES

239-253

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Wuppertal", 
          "id": "https://www.grid.ac/institutes/grid.7787.f", 
          "name": [
            "Physics Department, University of Wuppertal, Gauss-Strasse 20, D-5600, Wuppertal 1"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grassberger", 
        "givenName": "P.", 
        "id": "sg:person.0704113004.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0704113004.84"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Wuppertal", 
          "id": "https://www.grid.ac/institutes/grid.7787.f", 
          "name": [
            "Physics Department, University of Wuppertal, Gauss-Strasse 20, D-5600, Wuppertal 1"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Freund", 
        "givenName": "H.", 
        "id": "sg:person.010651627717.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010651627717.43"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01919172", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007999202", 
          "https://doi.org/10.1007/bf01919172"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01919172", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007999202", 
          "https://doi.org/10.1007/bf01919172"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230130406", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021259969"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1024857777", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-51576-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024857777", 
          "https://doi.org/10.1007/978-3-642-51576-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-51576-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024857777", 
          "https://doi.org/10.1007/978-3-642-51576-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0305004100034095", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053989030"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/jphyslet:019850046017077100", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1057009872"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1088/0305-4470/13/8/005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059065362"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1088/0305-4470/15/2/033", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059066023"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1088/0305-4470/21/16/004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059069623"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1088/0305-4470/22/18/036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059070413"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.56.1148", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060792839"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.56.1148", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060792839"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.57.2203", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060794036"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.57.2203", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060794036"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.57.2607", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060794166"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.57.2607", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060794166"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.58.86", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060795415"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.58.86", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060795415"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.60.1591", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060796798"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.60.1591", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060796798"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1126/science.220.4598.671", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062526985"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1209/0295-5075/2/12/005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064229072"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.21.2.498", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064728333"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4153/cjm-1965-045-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072264662"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/ro/1986200301771", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1083713868"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1990-07", 
    "datePublishedReg": "1990-07-01", 
    "description": "We give a new heuristic algorithm for minimum matching problems and apply it to the Euclidean problem with random vertices in 2 dimensions. The algorithm is based on simulated annealing and performs in practice faster than previous heuristic algorithms yielding suboptimal solutions of the same good quality. From configurations with up toN=20.000 vertices in the unit square we estimate that the length of a minimum matching scales asymptotically asL\u223c\u0392\u221aN with (\u0392=0.3123\u00b10.0016.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01416735", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "name": "An efficient heuristic algorithm for minimum matching", 
    "pagination": "239-253", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "8f2d2e651c99dc1ded0ece00ada262d55fe708d1781dd56044021315d11529c6"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01416735"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030054364"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01416735", 
      "https://app.dimensions.ai/details/publication/pub.1030054364"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:28", 
    "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/0000000370_0000000370/records_46741_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01416735"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

118 TRIPLES      20 PREDICATES      44 URIs      17 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01416735 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N8dedb050579c4d9db23e36f944a75bba
4 schema:citation sg:pub.10.1007/978-3-642-51576-7
5 sg:pub.10.1007/bf01919172
6 https://app.dimensions.ai/details/publication/pub.1024857777
7 https://doi.org/10.1002/net.3230130406
8 https://doi.org/10.1017/s0305004100034095
9 https://doi.org/10.1051/jphyslet:019850046017077100
10 https://doi.org/10.1051/ro/1986200301771
11 https://doi.org/10.1088/0305-4470/13/8/005
12 https://doi.org/10.1088/0305-4470/15/2/033
13 https://doi.org/10.1088/0305-4470/21/16/004
14 https://doi.org/10.1088/0305-4470/22/18/036
15 https://doi.org/10.1103/physrevlett.56.1148
16 https://doi.org/10.1103/physrevlett.57.2203
17 https://doi.org/10.1103/physrevlett.57.2607
18 https://doi.org/10.1103/physrevlett.58.86
19 https://doi.org/10.1103/physrevlett.60.1591
20 https://doi.org/10.1126/science.220.4598.671
21 https://doi.org/10.1209/0295-5075/2/12/005
22 https://doi.org/10.1287/opre.21.2.498
23 https://doi.org/10.4153/cjm-1965-045-4
24 schema:datePublished 1990-07
25 schema:datePublishedReg 1990-07-01
26 schema:description We give a new heuristic algorithm for minimum matching problems and apply it to the Euclidean problem with random vertices in 2 dimensions. The algorithm is based on simulated annealing and performs in practice faster than previous heuristic algorithms yielding suboptimal solutions of the same good quality. From configurations with up toN=20.000 vertices in the unit square we estimate that the length of a minimum matching scales asymptotically asL∼Β√N with (Β=0.3123±0.0016.
27 schema:genre research_article
28 schema:inLanguage en
29 schema:isAccessibleForFree false
30 schema:name An efficient heuristic algorithm for minimum matching
31 schema:pagination 239-253
32 schema:productId N01a8efcdb5464226bed567c94a30cff8
33 N083c0de09fbd4763aa259be6788ff7da
34 Nb575ed93da8447e88f220d1bbaa717d7
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030054364
36 https://doi.org/10.1007/bf01416735
37 schema:sdDatePublished 2019-04-11T13:28
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N616ad4fdad3b411da93340bd343d3888
40 schema:url http://link.springer.com/10.1007/BF01416735
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N01a8efcdb5464226bed567c94a30cff8 schema:name readcube_id
45 schema:value 8f2d2e651c99dc1ded0ece00ada262d55fe708d1781dd56044021315d11529c6
46 rdf:type schema:PropertyValue
47 N083c0de09fbd4763aa259be6788ff7da schema:name doi
48 schema:value 10.1007/bf01416735
49 rdf:type schema:PropertyValue
50 N616ad4fdad3b411da93340bd343d3888 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N80e4730bc935480e92d1dcc281f54a1d rdf:first sg:person.010651627717.43
53 rdf:rest rdf:nil
54 N8dedb050579c4d9db23e36f944a75bba rdf:first sg:person.0704113004.84
55 rdf:rest N80e4730bc935480e92d1dcc281f54a1d
56 Nb575ed93da8447e88f220d1bbaa717d7 schema:name dimensions_id
57 schema:value pub.1030054364
58 rdf:type schema:PropertyValue
59 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
60 schema:name Information and Computing Sciences
61 rdf:type schema:DefinedTerm
62 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
63 schema:name Artificial Intelligence and Image Processing
64 rdf:type schema:DefinedTerm
65 sg:person.010651627717.43 schema:affiliation https://www.grid.ac/institutes/grid.7787.f
66 schema:familyName Freund
67 schema:givenName H.
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010651627717.43
69 rdf:type schema:Person
70 sg:person.0704113004.84 schema:affiliation https://www.grid.ac/institutes/grid.7787.f
71 schema:familyName Grassberger
72 schema:givenName P.
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0704113004.84
74 rdf:type schema:Person
75 sg:pub.10.1007/978-3-642-51576-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024857777
76 https://doi.org/10.1007/978-3-642-51576-7
77 rdf:type schema:CreativeWork
78 sg:pub.10.1007/bf01919172 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007999202
79 https://doi.org/10.1007/bf01919172
80 rdf:type schema:CreativeWork
81 https://app.dimensions.ai/details/publication/pub.1024857777 schema:CreativeWork
82 https://doi.org/10.1002/net.3230130406 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021259969
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1017/s0305004100034095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053989030
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1051/jphyslet:019850046017077100 schema:sameAs https://app.dimensions.ai/details/publication/pub.1057009872
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1051/ro/1986200301771 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083713868
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1088/0305-4470/13/8/005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059065362
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1088/0305-4470/15/2/033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059066023
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1088/0305-4470/21/16/004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059069623
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1088/0305-4470/22/18/036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059070413
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1103/physrevlett.56.1148 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060792839
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1103/physrevlett.57.2203 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060794036
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1103/physrevlett.57.2607 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060794166
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1103/physrevlett.58.86 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060795415
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1103/physrevlett.60.1591 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060796798
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1126/science.220.4598.671 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062526985
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1209/0295-5075/2/12/005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064229072
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1287/opre.21.2.498 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728333
113 rdf:type schema:CreativeWork
114 https://doi.org/10.4153/cjm-1965-045-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072264662
115 rdf:type schema:CreativeWork
116 https://www.grid.ac/institutes/grid.7787.f schema:alternateName University of Wuppertal
117 schema:name Physics Department, University of Wuppertal, Gauss-Strasse 20, D-5600, Wuppertal 1
118 rdf:type schema:Organization
 




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


...