On the existence of weak greedy matching heuristics (Q1080871)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the existence of weak greedy matching heuristics |
scientific article |
Statements
On the existence of weak greedy matching heuristics (English)
0 references
1986
0 references
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.
0 references
approximate algorithms
0 references
complexity
0 references
heuristics
0 references
minimum weight perfect matching
0 references
0 references
