On the existence of weak greedy matching heuristics (Q1080871)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3968627
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the existence of weak greedy matching heuristics |
scientific article; zbMATH DE number 3968627 |
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
0.8844068646430969
0 references
0.8712970018386841
0 references
0.8712970018386841
0 references
