### Abstract

We give a class of heuristic algorithms for minimum weight perfect matching on a complete edge-weighted graph K(V) satisfying the triangle inequality, where V is a set of an even number, n, of vertices. This class is a generalization of the Onethird heuristics, the hypergreedy heuristic, and it possibly employs any given exact or approximate perfect matching algorithm as an auxiliary heuristic to an appropriate subgraph of K(V). In particularly using the heuristic of Gabow et al. [3] as its auxiliary heuristic, our algorithm can obtain a solution whose weight is at most (3/2 log_{3} log_{3} log_{3} n + 2) times the weight of the optimal solution in O (n^{2} log log log n) time, or a solution with an error of 3(log_{3} log_{3} n)^{0.125} - 1 in O(n_{2}) time.

Original language | English (US) |
---|---|

Pages (from-to) | 544-559 |

Number of pages | 16 |

Journal | Algorithmica (New York) |

Volume | 18 |

Issue number | 4 |

DOIs | |

State | Published - Jan 1 1997 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Computer Science Applications
- Applied Mathematics

### Cite this

}

*Algorithmica (New York)*, vol. 18, no. 4, pp. 544-559. https://doi.org/10.1007/PL00009172

**A General Class of Heuristics for Minimum Weight Perfect Matching and Fast Special Cases with Doubly and Triply Logarithmic Errors.** / Imielińska, C.; Kalantari, Bahman.

Research output: Contribution to journal › Article

TY - JOUR

T1 - A General Class of Heuristics for Minimum Weight Perfect Matching and Fast Special Cases with Doubly and Triply Logarithmic Errors

AU - Imielińska, C.

AU - Kalantari, Bahman

PY - 1997/1/1

Y1 - 1997/1/1

N2 - We give a class of heuristic algorithms for minimum weight perfect matching on a complete edge-weighted graph K(V) satisfying the triangle inequality, where V is a set of an even number, n, of vertices. This class is a generalization of the Onethird heuristics, the hypergreedy heuristic, and it possibly employs any given exact or approximate perfect matching algorithm as an auxiliary heuristic to an appropriate subgraph of K(V). In particularly using the heuristic of Gabow et al. [3] as its auxiliary heuristic, our algorithm can obtain a solution whose weight is at most (3/2 log3 log3 log3 n + 2) times the weight of the optimal solution in O (n2 log log log n) time, or a solution with an error of 3(log3 log3 n)0.125 - 1 in O(n2) time.

AB - We give a class of heuristic algorithms for minimum weight perfect matching on a complete edge-weighted graph K(V) satisfying the triangle inequality, where V is a set of an even number, n, of vertices. This class is a generalization of the Onethird heuristics, the hypergreedy heuristic, and it possibly employs any given exact or approximate perfect matching algorithm as an auxiliary heuristic to an appropriate subgraph of K(V). In particularly using the heuristic of Gabow et al. [3] as its auxiliary heuristic, our algorithm can obtain a solution whose weight is at most (3/2 log3 log3 log3 n + 2) times the weight of the optimal solution in O (n2 log log log n) time, or a solution with an error of 3(log3 log3 n)0.125 - 1 in O(n2) time.

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

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

U2 - 10.1007/PL00009172

DO - 10.1007/PL00009172

M3 - Article

VL - 18

SP - 544

EP - 559

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -