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

M. D. Grigoriadis, Bahman Kalantari

Research output: Contribution to journalArticle

4 Citations (Scopus)

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.

Original languageEnglish (US)
Pages (from-to)73-76
Number of pages4
JournalInformation Processing Letters
Volume22
Issue number2
DOIs
StatePublished - Jan 18 1986

Fingerprint

Matching Algorithm
Euclidean
Lower bound
Time Complexity
Heuristic algorithms
Perfect Matching
Matching Problem
Exact Algorithms
Heuristic algorithm
Sort

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

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.",
author = "Grigoriadis, {M. D.} and Bahman Kalantari",
year = "1986",
month = "1",
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",
number = "2",

}

A lower bound to the complexity of Euclidean and rectilinear matching algorithms. / Grigoriadis, M. D.; Kalantari, Bahman.

In: Information Processing Letters, Vol. 22, No. 2, 18.01.1986, p. 73-76.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Grigoriadis, M. D.

AU - Kalantari, Bahman

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.

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

VL - 22

SP - 73

EP - 76

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 2

ER -