A lower bound to the complexity of Euclidean and rectilinear matching algorithms
type: Item
instance of: scholarly article
title: A lower bound to the complexity of Euclidean and rectilinear matching algorithms
zbMATH Open document ID: 0587.68062
DOI: 10.1016/0020-0190(86)90143-2
author: Bahman Kalantari
author: M. D. Grigoriadis
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
review text: 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 \({\mathbb{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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 3943047
zbMATH Keywords: networks
zbMATH Keywords: sorting
zbMATH Keywords: spanning trees
zbMATH Keywords: worst-case time complexity
zbMATH Keywords: minimum- weight perfect matching
MaRDI profile type: Publication
full work available at URL: 0020-0190(86)90143-2
OpenAlex ID: W2048659526
cites work: A survey of heuristics for the weighted matching problem
cites work: Decomposable searching problems I. Static-to-dynamic transformation
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Q4130999
cites work: Q3219751
cites work: Q4739657
cites work: Heuristic matching for graphs satisfying the triangle inequality
cites work: On a Greedy Heuristic for Complete Matching
cites work: Combinatorial Problems: Reductibility and Approximation
cites work: Q4010349
description: scientific article; zbMATH DE number 3943047