A NEW CLASS OF HEURISTIC ALGORITHMS FOR WEIGHTED PERFECT MATCHING

被引：4

作者：

GRIGORIADIS, MD

KALANTARI, B

机构：

[1] Rutgers State Univ of New Jersey, United States

来源：

JOURNAL OF THE ACM | 1988年 / 35卷 / 04期

关键词：

Computer Programming - Algorithms - Optimization;

D O I：

10.1145/48014.48015

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The minimum-weight perfect matching problem for complete graphs of n vertices with edge weights satisfying the triangle inequality is considered. For each nonnegative integer k &le log3n, and for any perfect matching algorithm that runs in t(n) time and has an error bound of f(n) times the optimal weight, an O(max{n2,t(3-kn)}))-time heuristic algorithm with an error bound of (7/3)k(1+f(3-kn))-1 is given. By the selection of k as appropriate functions of n, heuristics that have better running times and/or error bounds than existing ones are derived.

引用

页码：769 / 776

页数：8