On the existence of weak greedy matching heuristics

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

Research output: Contribution to journalArticle

3 Citations (Scopus)

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 - Jan 1 1986

Fingerprint

Heuristics
Greedy Heuristics
Triangle inequality
Perfect Matching
Complete Graph
Approximate Solution
Optimal Solution
Optimal solution
Graph

All Science Journal Classification (ASJC) codes

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

Cite this

Grigoriadis, M. D. ; Kalantari, Bahman ; Lai, C. Y. / On the existence of weak greedy matching heuristics. In: Operations Research Letters. 1986 ; Vol. 5, No. 4. pp. 201-205.
@article{e321110a952947c898c6eae6f0e12c66,
title = "On the existence of weak greedy matching heuristics",
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.",
author = "Grigoriadis, {M. D.} and Bahman Kalantari and Lai, {C. Y.}",
year = "1986",
month = "1",
day = "1",
doi = "10.1016/0167-6377(86)90078-7",
language = "English (US)",
volume = "5",
pages = "201--205",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "4",

}

On the existence of weak greedy matching heuristics. / Grigoriadis, M. D.; Kalantari, Bahman; Lai, C. Y.

In: Operations Research Letters, Vol. 5, No. 4, 01.01.1986, p. 201-205.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the existence of weak greedy matching heuristics

AU - Grigoriadis, M. D.

AU - Kalantari, Bahman

AU - Lai, C. Y.

PY - 1986/1/1

Y1 - 1986/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0022796250&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022796250&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(86)90078-7

DO - 10.1016/0167-6377(86)90078-7

M3 - Article

VL - 5

SP - 201

EP - 205

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 4

ER -