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

C. Imielińska, Bahman Kalantari

Research output: Contribution to journalArticle

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

Original languageEnglish (US)
Pages (from-to)544-559
Number of pages16
JournalAlgorithmica (New York)
Volume18
Issue number4
DOIs
StatePublished - Jan 1 1997

Fingerprint

Perfect Matching
Heuristic algorithms
Logarithmic
Heuristics
Heuristic algorithm
Triangle inequality
Even number
Weighted Graph
Matching Algorithm
Subgraph
Optimal Solution
Class

All Science Journal Classification (ASJC) codes

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

Cite this

@article{ba51b5a9986841f88e0027ac5d9e5fd1,
title = "A General Class of Heuristics for Minimum Weight Perfect Matching and Fast Special Cases with Doubly and Triply Logarithmic Errors",
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 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.",
author = "C. Imielińska and Bahman Kalantari",
year = "1997",
month = "1",
day = "1",
doi = "10.1007/PL00009172",
language = "English (US)",
volume = "18",
pages = "544--559",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "4",

}

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.

In: Algorithmica (New York), Vol. 18, No. 4, 01.01.1997, p. 544-559.

Research output: Contribution to journalArticle

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 -