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

Abstract

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
Volume5
Issue number4
DOIs
StatePublished - Oct 1986

All Science Journal Classification (ASJC) codes

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

Keywords

  • approximate algorithms
  • complexity
  • heuristics
  • weighted perfect mathing

Fingerprint

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

Cite this