On the existence of weak greedy matching heuristics

M. D. Grigoriadis, B. Kalantari, C. Y. Lai

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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 valued functions which depend only on n.

Original languageEnglish (US)
Pages (from-to)201-205
Number of pages5
JournalOperations Research Letters
Issue number4
StatePublished - Oct 1986

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


  • approximate algorithms
  • complexity
  • heuristics
  • weighted perfect mathing


Dive into the research topics of 'On the existence of weak greedy matching heuristics'. Together they form a unique fingerprint.

Cite this