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
相关论文
共 22 条
[11]   A LOWER BOUND TO THE COMPLEXITY OF EUCLIDEAN AND RECTILINEAR MATCHING ALGORITHMS [J].
GRIGORIADIS, MD ;
KALANTARI, B .
INFORMATION PROCESSING LETTERS, 1986, 22 (02) :73-76
[12]   SOLVING MATCHING PROBLEMS WITH LINEAR-PROGRAMMING [J].
GROTSCHEL, M ;
HOLLAND, O .
MATHEMATICAL PROGRAMMING, 1985, 33 (03) :243-259
[13]  
IRI M, 1983, NETWORKS, V13, P62
[14]  
Lawler E.L., 1976, COMBINATORIAL OPTIMI
[15]  
Papadimitriou C. H., 1998, COMBINATORIAL OPTIMI
[16]   HEURISTIC MATCHING FOR GRAPHS SATISFYING THE TRIANGLE INEQUALITY [J].
PLAISTED, DA .
JOURNAL OF ALGORITHMS, 1984, 5 (02) :163-179
[17]  
Preparata FP, 2012, COMPUTATIONAL GEOMET
[18]   ON A GREEDY HEURISTIC FOR COMPLETE MATCHING [J].
REINGOLD, EM ;
TARJAN, RE .
SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :676-681
[19]  
SUPOWIT KJ, 1980, 12TH P ANN ACM S THE, P398
[20]  
Vaidya P. M., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P117, DOI 10.1109/SFCS.1986.8
123