### 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 | |

State | Published - Jan 18 1986 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Computational Theory and Mathematics

### Cite this

*Information Processing Letters*,

*22*(2), 73-76. https://doi.org/10.1016/0020-0190(86)90143-2

}

*Information Processing Letters*, vol. 22, no. 2, pp. 73-76. https://doi.org/10.1016/0020-0190(86)90143-2

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

Research output: Contribution to journal › Article

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 -