On the existence of weak greedy matching heuristics

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

doi:https://doi.org/10.1016/0167-6377(86)90078-7

On the existence of weak greedy matching heuristics

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

School of Arts and Sciences, Computer Science

Rutgers, The State University

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	201-205
Number of pages	5
Journal	Operations Research Letters
Volume	5
Issue number	4
DOIs	https://doi.org/10.1016/0167-6377(86)90078-7
State	Published - Oct 1986

ASJC Scopus subject areas

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

Keywords

approximate algorithms
complexity
heuristics
weighted perfect mathing

Access to Document

https://doi.org/10.1016/0167-6377(86)90078-7

Cite this

@article{3010c3bbe4c54628a66ce815d7141405,

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.",

keywords = "approximate algorithms, complexity, heuristics, weighted perfect mathing",

author = "Grigoriadis, {M. D.} and B. Kalantari and Lai, {C. Y.}",

note = "Funding Information: * This research was supported in part by the lqational Science Foundation under Grant no. MCS-8113503.",

year = "1986",

month = oct,

doi = "https://doi.org/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",

}

TY - JOUR

T1 - On the existence of weak greedy matching heuristics

AU - Grigoriadis, M. D.

AU - Kalantari, B.

AU - Lai, C. Y.

N1 - Funding Information: * This research was supported in part by the lqational Science Foundation under Grant no. MCS-8113503.

PY - 1986/10

Y1 - 1986/10

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.

KW - approximate algorithms

KW - complexity

KW - heuristics

KW - weighted perfect mathing

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 - https://doi.org/10.1016/0167-6377(86)90078-7

DO - https://doi.org/10.1016/0167-6377(86)90078-7

M3 - Article

SN - 0167-6377

VL - 5

SP - 201

EP - 205

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

On the existence of weak greedy matching heuristics

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this