A lower bound to the complexity of Euclidean and rectilinear matching algorithms

M. D. Grigoriadis; B. Kalantari

doi:10.1016/0020-0190(86)90143-2

A lower bound to the complexity of Euclidean and rectilinear matching algorithms

M. D. Grigoriadis, B. Kalantari

School of Arts and Sciences, Computer Science

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

The worst-case time complexity of any exact algorithm for the Euclidean or rectilinear minimum-weight perfect matching problem, which takes as input the list of coordinates of n points in R^k, is shown to be bounded below by the infimum of the worst-case time complexities of all algorithms which sort n real numbers. This result also applies to any heuristic algorithm for which the worst-case ratio of the weight of the approximate matching it produces to the weight of the optimal matching only depends upon n.

Original language	English (US)
Pages (from-to)	73-76
Number of pages	4
Journal	Information Processing Letters
Volume	22
Issue number	2
DOIs	https://doi.org/10.1016/0020-0190(86)90143-2
State	Published - Jan 18 1986

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Complexity
graphs
matching
networks
sorting
spanning trees

Access to Document

10.1016/0020-0190(86)90143-2

Cite this

@article{fe1e8eb78db54d599f0affd9543ebdc3,

title = "A lower bound to the complexity of Euclidean and rectilinear matching algorithms",

abstract = "The worst-case time complexity of any exact algorithm for the Euclidean or rectilinear minimum-weight perfect matching problem, which takes as input the list of coordinates of n points in Rk, is shown to be bounded below by the infimum of the worst-case time complexities of all algorithms which sort n real numbers. This result also applies to any heuristic algorithm for which the worst-case ratio of the weight of the approximate matching it produces to the weight of the optimal matching only depends upon n.",

keywords = "Complexity, graphs, matching, networks, sorting, spanning trees",

author = "Grigoriadis, {M. D.} and B. Kalantari",

note = "Funding Information: There has also been a continuing interest in low-order heuristic algorithms for MP. The performance of a heuristic is usually ascertained by considering its time complexity for generating an * This research was supported in part by the National Science Foundation under Grant No. MCS-8113503.",

year = "1986",

month = jan,

day = "18",

doi = "10.1016/0020-0190(86)90143-2",

language = "English (US)",

volume = "22",

pages = "73--76",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - A lower bound to the complexity of Euclidean and rectilinear matching algorithms

AU - Grigoriadis, M. D.

AU - Kalantari, B.

N1 - Funding Information: There has also been a continuing interest in low-order heuristic algorithms for MP. The performance of a heuristic is usually ascertained by considering its time complexity for generating an * This research was supported in part by the National Science Foundation under Grant No. MCS-8113503.

PY - 1986/1/18

Y1 - 1986/1/18

N2 - The worst-case time complexity of any exact algorithm for the Euclidean or rectilinear minimum-weight perfect matching problem, which takes as input the list of coordinates of n points in Rk, is shown to be bounded below by the infimum of the worst-case time complexities of all algorithms which sort n real numbers. This result also applies to any heuristic algorithm for which the worst-case ratio of the weight of the approximate matching it produces to the weight of the optimal matching only depends upon n.

AB - The worst-case time complexity of any exact algorithm for the Euclidean or rectilinear minimum-weight perfect matching problem, which takes as input the list of coordinates of n points in Rk, is shown to be bounded below by the infimum of the worst-case time complexities of all algorithms which sort n real numbers. This result also applies to any heuristic algorithm for which the worst-case ratio of the weight of the approximate matching it produces to the weight of the optimal matching only depends upon n.

KW - Complexity

KW - graphs

KW - matching

KW - networks

KW - sorting

KW - spanning trees

UR - http://www.scopus.com/inward/record.url?scp=0022443090&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022443090&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(86)90143-2

DO - 10.1016/0020-0190(86)90143-2

M3 - Article

AN - SCOPUS:0022443090

SN - 0020-0190

VL - 22

SP - 73

EP - 76

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

A lower bound to the complexity of Euclidean and rectilinear matching algorithms

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this