On the existence of weak greedy matching heuristics
type: Item
instance of: scholarly article
title: On the existence of weak greedy matching heuristics
zbMATH Open document ID: 0601.05038
DOI: 10.1016/0167-6377(86)90078-7
author: B. George
published in: Operations Research Letters
publication date: 1986-01-01T00:00:00Z
review text: We exhibit an exponential number of greedy heuristics for minimum weight perfect matching of complete graphs of n vertices with edge weights satisfying the triangle inequality. The ratio of the weight of an approximate solution obtained by these heuristics to that of an optimal solution is shown to be bounded above by finite and valued functions which depend only on n.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 3968627
zbMATH Keywords: approximate algorithms
zbMATH Keywords: complexity
zbMATH Keywords: heuristics
zbMATH Keywords: minimum weight perfect matching
MaRDI profile type: Publication
full work available at URL: 0167-6377(86)90078-7
OpenAlex ID: W1987379377
cites work: A survey of heuristics for the weighted matching problem
cites work: Decomposable searching problems I. Static-to-dynamic transformation
cites work: Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Paths, Trees, and Flowers
cites work: A lower bound to the complexity of Euclidean and rectilinear matching algorithms
cites work: Linear-time approximation algorithms for finding the minimum-weight perfect matching on a plane
cites work: Q4130999
cites work: Heuristic matching for graphs satisfying the triangle inequality
cites work: On a Greedy Heuristic for Complete Matching
description: scientific article; zbMATH DE number 3968627