### 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 - Aug 1997 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

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

### Keywords

- Heuristic algorithms
- Perfect matching

### 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, B.

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

PY - 1997/8

Y1 - 1997/8

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.

KW - Heuristic algorithms

KW - Perfect matching

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

AN - SCOPUS:0346969503

VL - 18

SP - 544

EP - 559

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -